Happy New Year 11111011110 | Online Programming Contest

Charlie Bucket is a loving and kind boy, who lives in poverty with his mother, father and four bedridden grandparents. Down the street, there is Willy Wonka’s chocolate factory who is famous for both his chocolates and the factory. After long years of conducting business with chocolate, now Wonka finally decided to make an heir to the factory.

So, instead of putting golden tickets in ordinary Wonka bars (which is old fashioned...:P) he decided to take a programming contest to choose 5 candidates for the heir. And, then he will give a tough problem to them (among these five) and the first to answer will be the winner.

After taking the contest Wonka eventually gets his five candidates and Charlie is one of them. Now, before throwing the heir deciding problem towards them he decided to give them 2 hints.

1st hint is an algorithm whose pseudo code is given below

    # 'array' is 1-indexed
    def MakeNewArray(array, d):
        if d == 1:
            return array
        else:
            array = MakeNewArray(array, d-1)
            new_array = [array[array[i]] for i in 1..inf]
            return new_array

For example, if array = [2, 3, 5, 7, 11, ...], then MakeNewArray(array, 2) = [3, 5, 11, ...].

2nd hint is Kuddus array. A Kuddus array is a sorted array of Kuddus numbers. Kuddus numbers are such prime numbers which can be expressed as the summation of squares of two distinct positive integers.For, example 5 can be expressed as 1²+2². So it is a Kuddus number. Also 13 (3² + 2²) and 17 (4² + 1²) are Kuddus number. So, first few numbers of Kuddus array are 5, 13, 17 ... etc.

Now, it’s time for the heir deciding problem. The problem is as follows. There are n boxes and all of them are initially empty (no chocolate). Now in every step (starts from 1st step to the last) Wonka will do some sets of operation. The operation are of four kinds. The operation is indicated by an integer op.

• If op=1. Then it is an add operation and it is followed by two integers a, b. It means Wonka will add b chocolates in box number a.
• If op=2. Then it is a multiplication operation which is also followed by two integers a, b. It means Wonka will multiply the number of chocolates in box number a by b.
• If op=3. Then it is a swap operation which is also followed by a, b. It means the boxes a and b will exchange their chocolates.
• If op=4. Then it is a clear operation which is followed by only a single integer a. This means Wonka will remove all chocolates from box a.

There are 2 sets of operation. One is an ordinary set and another is special set. In normal steps he will perform the ordinary set of operation serially (as it appears in the input). And in the special steps he will perform the special set of operation serially. Special step number is stored in an array called Special array.

More precisely, he has an array named Special of infinite numbers. It is a sorted array. The elements of the array are denoted by Special[1], Special[2], Special[3]...etc [normal array system]. So he will perform the special operation only at Special[1]th, Special[2]th, Special[3]th ... etc steps.

Now:

Special := MakeNewArray(Kuddus, d).

Here MakeNewArray and Kuddus are described previously. d is an integer which will be given in the input. At last Wonka will tell the number of steps s.

Now, Charlie is busy in some other works. So, he needs your help. You will have to answer after s steps what is the total number of chocolates in all the boxes (summation of all the chocolates in every box).

Input

Input consists of some test cases (not more than 15).

Every case begins with two integer n (>= 2) and d (1 <= d <= 5). Then there is an integer op1 which denotes the number of operation for ordinary steps. The next op1 lines each contain a number op (1 <= op <= 4) and if op<=3 then it is followed by two integers a and b, otherwise (op=4) it is followed by a. The meaning of them is described above. Then there is another integer op2 which denotes the number of operations for special steps and the next op2 steps is also followed by same format of input as op1 is followed.Finally comes the number of steps s (1 <= s <= 10⁸).

The meaning of every symbol is described above. Every input is a non-negative integer and not more than 1000 unless stated otherwise. There are no illegal input (i.e. there is no illegal box where operation will be performed). It is also guaranteed that there are equal number of cases for each possible values of d and n <= 2 * d².

Output

For each test case the answer will be just a single line denoting the total number of chocolates in the boxes after s steps. You should return the answer % 2⁶⁴.

Example

Input:
2 1
5
1 1 1
1 2 1
2 1 2
2 2 3
3 1 2
3
1 1 1
1 2 1
3 1 2
4

2 1
5
1 1 1
1 2 1
2 1 2
2 2 3
3 1 2
3
1 1 1
1 2 1
3 1 2
5

Output:
119
121

Problem Setter: Syed Shahriar Manjur, Special Thanks: Nafis Ahmed