Каждый год сыроделы собираются на выставке сыров, чтобы показать свои разработки. У каждого сыродела на выставке есть свой стенд, на котором он выкладывает в ряд кусочки сыра на пробу. Всего на выставке будет N стендов, пронумерованных от 1 до N, причём на стенде с номером i будут лежать k_i кусочков сыра. На выставке будет много разных сыров, но их можно разбить на типы: например, сычужные, кисломолочные, сывороточные и другие. У одного сыродела на стенде могут быть кусочки разных типов сыра.

Клан крыс-гурманов знает, когда и где будет проводиться выставка. У каждой крысы есть любимый тип сыра, и она отказывается есть любые другие сыры. Глава клана Умка имеет большой опыт в краже сыра. Она знает, что если все крысы одновременно ворвутся в зал, начнётся переполох. Сыра тогда много не унесёшь, а из-за усиления охраны на следующую выставку можно вообще не попасть. Поэтому она решила, что крысы будут ходить по одной. Каждая крыса должна обежать все стенды и с каждого стащить ровно один крайний кусочек сыра, если он любимого ей типа.

Всего за сыром отправятся Q крыс. Каждая крыса выбегает либо с левой, либо с правой стороны зала, и ко всем стендам она подбегает с той же стороны. То есть если она выбегает слева, то у каждого стенда она смотрит на самый левый кусочек сыра. Если этот кусочек её любимого типа, она его берёт. Если крыса выбегает справа, она действует так же, только смотрит на каждом стенде на самый правый кусочек сыра. Пустые стенды крысы пропускают. Следующая крыса отправляется только после того, как предыдущая закончит свой обход. Крысы отправятся до открытия выставки, поэтому во время обходов никто, кроме крыс, брать сыр не будет.

Умка заранее узнала, какие кусочки сыра будут лежать на каждом стенде и в каком порядке. Также Умка знает любимый тип сыра каждой крысы, и она уже распланировала, кто за кем побежит и с какой стороны. Помогите Умке определить для каждой крысы номера всех стендов, с которых она заберёт сыр.

В первой строке даны два целых числа N и Q (1 ≤ N, Q ≤ 10⁵) — количество стендов и количество крыс.

В следующих N строках описаны кусочки сыра на стендах. В i-й из этих строк сначала дано целое число k_i (1 ≤ k_i ≤ 10⁵), затем k_i целых чисел a_i,1, a_i,2, ..., a_i,ki (1 ≤ a_i,j ≤ 10⁹) — типы кусочков сыра на стенде с номером i в порядке слева направо. Сумма всех k_i не превосходит 10⁵.

В следующих Q строках описаны крысы в том порядке, в котором они отправятся за сыром. Каждая строка содержит два целых числа s и x (s ∈ {1, 2}, 1 ≤ x ≤ 10⁹) — сторону, с которой выбегает крыса, и её любимый тип сыра. Если s=1, крыса выбегает слева, если s=2, то выбегает справа.

Для каждой крысы в порядке обходов выведите отдельную строку. В ней сначала выведите количество стендов, с которых она заберёт сыр, затем номера этих стендов в порядке возрастания.