Every year, cheese makers gather at the cheese exhibition to showcase their creations. Each cheese maker has their own booth at the exhibition, where they arrange pieces of cheese in a row for tasting. In total, there will be N booths, numbered from 1 to N, and booth number i will have k_i pieces of cheese. There will be many different cheeses at the exhibition, but they can be divided into types: for example, rennet cheese, sour milk cheese, whey cheese and others. A cheese maker’s booth may have pieces of different cheese types.

A clan of gourmet rats knows when and where the exhibition will take place. Each rat has a favorite cheese type and refuses to eat any other cheese. The clan leader, Umka, has a lot of experience in stealing cheese. She knows that if all the rats rush into the hall at the same time, chaos will break out. Then they will not carry away much cheese, and because of increased security they may not get into the next exhibition at all. So she decided that the rats will go one at a time. Each rat must run past all the booths and steal exactly one outermost piece of cheese from each booth, if it is of its favorite type.

A total of Q rats will go after the cheese. Each rat runs out either from the left or from the right side of the hall, and approaches all booths from that same side. That is, if it runs from the left, then at each booth it looks at the leftmost piece of cheese. If this piece is of its favorite type, the rat takes it. If a rat runs from the right, it acts the same way, but looks at the rightmost piece of cheese at each booth. Empty booths are skipped. The next rat starts only after the previous one finishes. The rats will go before the exhibition opens, so nobody except the rats takes any cheese at this time.

Umka found out in advance which pieces of cheese will be on each booth and in which order. She also knows the favorite cheese type of each rat, and she has already planned who goes after whom and from which side. Help Umka find, for each rat, the numbers of all booths from which it will take cheese.

The first line contains two integers N and Q (1 ≤ N, Q ≤ 10⁵) — the number of booths and the number of rats.

The next N lines describe the pieces of cheese on the booths. In the i-th of these lines, first comes an integer k_i (1 ≤ k_i ≤ 10⁵), then k_i integers a_i,1, a_i,2, ..., a_i,ki (1 ≤ a_i,j ≤ 10⁹) — the types of the pieces of cheese on booth number i in left-to-right order. The sum of all k_i does not exceed 10⁵.

The next Q lines describe the rats in the order in which they will go for the cheese. Each line contains two integers s and x (s ∈ {1, 2}, 1 ≤ x ≤ 10⁹) — the side from which the rat runs out, and its favorite cheese type. If s=1, the rat runs out from the left; if s=2, the rat runs out from the right.

For each rat in the order in which they go, print a separate line. First print the number of booths from which the rat takes cheese, then the numbers of these booths in increasing order.