D. Приключения Алисы в картах
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса играет в карты с Дамой Червей, Королем Червей и Валетом Червей. В их карточной игре есть $$$n$$$ различных типов карт. В данный момент у Алисы есть карта типа $$$1$$$, и ей нужна карта типа $$$n$$$, чтобы сбежать из Страны Чудес. У остальных игроков есть по одной карте каждого типа.

В этой карточной игре Алиса может обмениваться картами с тремя другими игроками. У каждого игрока есть свои предпочтения среди этих $$$n$$$ типов, которые можно описать перестановками$$$^{\text{∗}}$$$ $$$q$$$, $$$k$$$ и $$$j$$$ для Дамы, Короля и Валета соответственно.

Игрок оценивает карту $$$a$$$ больше, чем карту $$$b$$$, если для их перестановки $$$p$$$, $$$p_a > p_b$$$. Тогда этот игрок готов обменять карту $$$b$$$ с Алисой в обмен на карту $$$a$$$. Предпочтения Алисы просты: она оценивает карту $$$a$$$ больше, чем карту $$$b$$$ если $$$a > b$$$, и она будет обмениваться картами только в соответствии с этими предпочтениями.

Определите, может ли Алиса обменять карту типа $$$1$$$ на карту типа $$$n$$$, учитывая эти предпочтения. Если это возможно, приведите возможный набор обменов для этого.

$$$^{\text{∗}}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$2\le n\le 2\cdot 10^5$$$) — количество типов карт.

Следующие три строки содержат предпочтения Дамы, Короля и Валета соответственно. Каждая из этих строк содержит $$$n$$$ целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1\le p_i\le n$$$) — перестановка, соответствующая предпочтениям игрока.

Сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных в первой строке выведите одну строку «YES» или «NO» (без кавычек), обозначающую, может ли Алиса обменяться на карту $$$n$$$.

Если первая строка была «YES», то на следующей строке выведите $$$k$$$ — количество обменов, которые сделает Алиса. На следующих $$$k$$$ строках выведите через пробел символ $$$c\in \{\texttt{q}, \texttt{k}, \texttt{j}\}$$$ и целое число $$$x$$$, обозначающее, что Алиса обменивается с игроком $$$c$$$, чтобы получить карту $$$x$$$. Должно быть так, что на $$$k$$$-й строке $$$x = n$$$. Если существует несколько решений, выведите любое из них.

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ. То же самое касается символа $$$c$$$, обозначающего игрока в обмене ($$$\texttt{Q}, \texttt{K}, \texttt{J}$$$ будут приняты наряду с их строчными вариантами).

Пример
Входные данные
2
3
1 3 2
2 1 3
1 2 3
4
2 3 1 4
1 2 3 4
1 4 2 3
Выходные данные
YES
2
k 2
q 3
NO
Примечание

В первом наборе входных данных Алиса может обменяться с Королем, чтобы получить карту $$$2$$$. Затем она может обменяться с Дамой, чтобы получить карту $$$3$$$.

Во втором наборе входных данных, хотя Алиса может обменяться с Дамой, чтобы получить карту $$$3$$$, с Королем, чтобы получить карту $$$2$$$, а затем с Валетом, чтобы получить карту $$$4$$$, это не является допустимым решением, так как оно не соответствует предпочтениям Алисы. Мы можем показать, что нет способа для Алисы получить карту $$$4$$$.