Warning: The original problem has a 2GB memory limit, but DMOJ only supports a 1GB memory limit. Solutions exist using less than 1GB of memory.
There are worms numbered from to . The length of a worm can be represented by a positive integer between and . You want to arrange the worms into several queues. Initially, each worm is in its own queue with only one worm (itself). Each worm is both at the front and at the end of its queue.
There are operations. Each operation is one of the following three types:
1 i j
where : Merge the queue worm is in with the queue worm is in. In the new queue, worm will be immediately after worm (and for the rest of the worms, the worm before/after them remains unchanged). It is guaranteed that worm is at the tail of some queue , worm is at the front of some queue, and are not in the same queue.2 i
where : Split the queue between worm and the worm immediately after . It is guaranteed that worm is not at the tail of some queue.3 s k
where is a positive integer and is a numeric string with length at least : Find the product of modulo where is over all substrings of length in . There are such substrings given and .
The definition of is given below.
For a given queue, the -string after worm is obtained by starting from worm , walking towards the tail of the queue, and finding the nearest worms to , including , and concatenating the lengths of these worms. If there are fewer than worms before reaching the tail, then worm won't have a -string. For example, if the numbers of worms in a queue are and they have lengths ; then the 3-string after worm is , worm does not have a 3-string, but its 2-string is and its 1-string is .
denotes the number of worms whose -string is exactly .
Input Specification
The first line consists of two positive integers denoting the number of worms and the number of operations.
In the second line, there are positive integers not exceeding denoting the length of worm .
In the following lines, each line specifies an operation.
The input file might be large.
Output Specification
For each operation 3 s k
, output a line with an integer denoting the output.
Sample Input 1
5 9
3 1 3 5 3
3 333135 2
3 333135 1
1 1 3
1 2 5
1 3 2
1 5 4
3 333135 2
3 333135 1
3 333135 3
Sample Output 1
0
81
1
81
0
Explanation for Sample 1
For the first query, since there is only one worm in each queue, no worms have a 2-string, so the output is simply .
For the second query, each worm's 1-string is the string formed by the worm's own length, so we see the 1-strings are (in no particular order) and the output is .
Sample Input 2
2 10
6 6
3 666666 1
1 1 2
3 666666 2
3 666666 4
3 666666666666666666666666666666 1
2 1
1 2 1
3 666666 2
3 666666 4
3 666666666666666666666666666666 1
Sample Output 2
64
1
0
75497471
1
0
75497471
Explanation for Sample 2
For the 4th and the 7th query, since is 6
s, is . Output it modulo .
Additional Samples
Constraints
.
Let denote the sum of lengths of in all queries. .
Let denote the number of operations of the form 2 i
, then .
The columns, from left to right, are:
- Test case
- Whether all lengths and all query strings are formed by
1
s.
Comments