eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Радость информатика

Радость информатика

Лимит времени 1 секунда
Лимит использования памяти 122 MiB

В этом году на олимпиаде по информатике участвуют n учеников. Участники пронумерованы от 1 до n.

С новой системой, они видят свои баллы сразу после отправки решения по задаче. От результата проверки, настроение участника может очень сильно измениться. В самом начале олимпиады, настроение всех участников равно единице.

Есть история изменений настроения участников. Жюри хочет контролировать настроение всех участников, и просит вас о помощи.

У вас есть запросы трех видов:

0 L R P - Жюри хочет знать произведение настроения всех участников, пронумерованных от L до R. Но так как это число может быть слишком большим, надо вывести его по модулю P;

1 L R X - Все участники с номерами от L до R узнали результат проверки и настроение каждого из них умножилось на число X;

2 L R X - Все участники с номерами от L до R, узнали результат проверки и настроение каждого из них поделилось на число X, гарантируется что настроение каждого участника на этом отрезке делится на число X.

Входные данные

В первой строке находятся числа n и m, количество участников и количество запросов. В следующих m строках описываются запросы. Известно, что во всех запросах 1LRn, 1X100, 1P10^9, 1n, m50000.

Выходные данные

Для каждого запроса типа 0, вывести ответ в отдельной строке.

Пример

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