Joy of computer scientist
This year n pupils participate at Informatics Olympiad. The participants are numbered from 1 to n.
With the new system, they see their points immediately after sending a solution to the task. From the result of the test, the mood of the participant can change very much. At the very beginning of the Olympics, the mood of all participants equals to one.
There is a history of changes in the mood of participants. The jury wants to control the mood of all participants, and asks you for help.
You have the queries of three types:
0 L R P - Jury wants to know the product of the mood of all the participants, numbered from L до R. This number can be big, so print it modulo P;
1 L R X - All participants with numbers from L to R learned the result of checking and the mood of each one is multiplied by the number X;
2 L R X - All participants with numbers from L to R, learned the result of checking and the mood of each one is divisible by the number X. It is guaranteed that the mood of each participant on this segment is divisible by X.
Input
First line contains numbers n and m, the number of participants and number of queries. Next m lines describe the queries. It is known that in all queries 1 ≤ L ≤ R ≤ n, 1 ≤ X ≤ 100, 1 ≤ P ≤ 10^9, 1 ≤ n, m ≤ 50000.
Output
For each query of type 0 print the answer in a separate line.