eolymp
bolt
Try our new interface for solving problems
Problems

Joy of computer scientist

Joy of computer scientist

Time limit 1 second
Memory limit 122 MiB

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 data

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 1LRn, 1X100, 1P10^9, 1n, m50000.

Output data

For each query of type 0 print the answer in a separate line.

Examples

Input example #1
5 5
0 1 5 1000000007
1 2 3 6
0 1 5 1000000007
2 2 3 3
0 1 5 1000000007
Output example #1
1
36
4
Input example #2
3 5
1 1 3 100
0 1 2 10
2 1 3 100
1 2 3 4
0 1 3 10
Output example #2
0
6
Source 2014 Казахстан, 4-й этап Республиканской олимпиады по информатике, Усть-Каменогорск, Март, Задача F