Due to unforeseen circumstances this task is not fifth.
A recent survey by polling agency found that no one likes the numbers from to . So we will focus on the next number, , and hope it does not follow the unfortunate fate of its predecessors.
Consider the following sequence in the positive and negative indices:
for each integer .
Note that equality uniquely defines both the positive and the negative indices (e.g. and )
You are given an array of numbers . Write a program that supports types of events:
with parameters . We want to find the value . Since it can get very large, print the answer modulo .
with parameters . Then the new value of becomes equal to for every .
输入格式
The first line of the standard input contains the numbers and .
The next line contains integers . Each of the following lines contains natural numbers .
If , then the line is a .
If , then the line is an and contains a further integer .
输出格式
For each , print on a new line the answer for that query.
样例
样例输入 1
1 5
1
1 1 1
2 1 1 -2
1 1 1
2 1 1 8
1 1 1
样例输出 1
1
100000521
1330
数据范围与提示
Sample Explanation
At the start and . After the first and . After the second and .
Constraints
Subtasks
Subtask
Points
Additional constraints
and only
and
and
None
The points for a subtask are given only if all tests for it and the required subtasks are passed successfully.
