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:
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.
The first line of the input contains two integers N and Q (1 ≤ N, Q ≤ 105), 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 si (1 ≤ si ≤ 216) indicating the size of the i-th snake, followed by si integers. The j-th integer cij ( - 109 ≤ cij ≤ 109) 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:
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 105.
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.
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.
## Input
The first line of the input contains two integers N and Q (1 ≤ N, Q ≤ 105), 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 si (1 ≤ si ≤ 216) indicating the size of the i-th snake, followed by si integers. The j-th integer cij ( - 109 ≤ cij ≤ 109) 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 ≤ sz) 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 105.
## 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.
[samples]
## 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.
**Definitions**
Let $ N \in \mathbb{Z}^+ $ be the number of elements.
Let $ p \in S_N $ be a given permutation (target).
Let $ k \in \mathbb{Z}^+ $ be the number of applications.
**Objective**
Count the number of permutations $ q \in S_N $ such that $ q^k = p $, modulo $ 10^9 + 7 $.