405302: GYM101875 K Little Teo's Playtime

K. Little Teo's Playtimetime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Little Teo is playing with colored magnets and made N colorful snakes numbered from 1 to N by sticking colored magnets one after another in a row. The number of magnets in each snake is a power of two because that makes them special.

Today, little Teo's playtime lasts Q minutes. Just looking at the snakes is boring and little Teo is hyperactive, so at each minute he may do one of four things:

1. Swap the x-th and y-th magnets of snake z;
2. Stick snake l to the left of snake r, both with the same size, forming a new snake with double the size, i.e., the rightmost magnet of snake l will stick to the leftmost magnet of snake r;
3. Split snake z in half;
4. Ask his nanny the size of the longest sequence of magnets with the same color in snake z.

Little Teo is a smart boy so he always chooses a snake with more than 1 magnet when swapping and splitting.

When little Teo sticks two snakes, the new snake gets numbered with the smallest positive number he didn't use yet; and when he splits a snake, the left part of the snake gets the smallest unused positive number and the right part gets the second smallest (see notes for clarity).

As his nanny, it is your duty to answer all of little Teo's questions so that he doesn't throw a tantrum, decreasing your already slim paycheck.

Input

The first line of the input contains two integers N and Q (1 ≤ N, Q ≤ 10⁵), indicating the number of snakes little Teo initially has and the number of minutes of little Teo's playtime.

Each of the following N lines starts with an integer s_i (1 ≤ s_i ≤ 2¹⁶) indicating the size of the i-th snake, followed by s_i integers. The j-th integer c_ij ( - 10⁹ ≤ c_ij ≤ 10⁹) represents the color of the j-th magnet of the i-th snake.

Each of the following Q lines describe what little Teo will do during his play time and has the following format:

• 1 x y z - Swap the x-th and y-th (1 ≤ x < y ≤ s_z) magnets of snake z;
• 2 l r - Stick snake l to the left of snake r (l ≠ r);
• 3 z - Split snake z in half;
• 4 z - Ask his nanny the size of the longest sequence of magnets with the same color in snake z.

It is guaranteed that the size of each snake is a power of two and that the sum of the sizes of the snakes doesn't exceed 10⁵.

Output

For each query of type 4, output in a separate line the size of the longest sequence of magnets with the same color in snake z.

ExampleInput

2 12
4 1 2 1 2
4 2 1 2 1
4 1
4 2
2 2 1
4 3
1 2 6 3
4 3
1 4 8 3
4 3
3 3
4 4
3 5
4 6

Output

1
1
2
4
4
4
2

Note

If little Teo starts with 3 snakes, they will be numbered 1, 2 and 3.

If he sticks snake 1 to snake 2, the new snake will be numbered 4.

If he afterwards splits snake 4, the left part will be numbered 5 and the right one will be numbered 6.