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
whereis 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