Julia found a series, , defined as:
For some integer (where ), she finds integers, , such that holds for all integers (where ):
She realized that the values of are not unique, so she only considers the tuple such that and is minimal. It is guaranteed that when and is minimal, there exists only one tuple .
Next, she defines and :
She then finds the following interesting property of :
where and are integers such that:
Julia wants you to answer queries in the following forms:
1 l r: Using and , print three space-separated integers denoting the respective values of , , and where:- is the total number of possible values of (where ) such that .
- is the total number of possible values of (where ) such that .
- is the total number of possible values of (where ) such that .
2 p u v: Find the value of modulo :
Input Format
The first line contains three space-separated integers describing the respective values of , , and .
Each line of the subsequent lines contains three or four space-separated values denoting a query asked by Julia.
Constraints
Output Format
Print lines of output where each line denotes the answer to query .
Sample Input
1 1 2
1 1 2
2 1 2 2
Sample Output
0 2 0
1
Explanation
The first few terms of series are , and:
Query 1 1 2:
The values of and are:
- For , , , and . So, and .
- For , , , , and . So, and .
So,
Now,
- , because for , no .
- , because for , each .
- , because for , no .
Thus, we print 0 2 0 (i.e., the respective values of , , and ) on a new line as the answer to Julia's query.
Query 2 1 2 2:
For , , , and :
Finally, we can find the value of :
Thus, we print 1 on a new line as the answer to Julia's query.