Республиканская олимпиада по информатике 2014 года за 9 класс | Казахстанские олимпиады

Задача F. Радость информатика

Ограничение по времени Ограничение по памяти
3 секунды 256 мегабайт

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

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

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

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

00 LL RR PP - Жюри хочет знать произведение настроения всех участников, пронумерованных от LL до RR. Но так как это число может быть слишком большим, надо вывести его по модулю PP

11 LL RR XX - Все участники с номерами от LL до RR узнали результат проверки и настроение каждого из них умножилось на число XX

22 LL RR XX - Все участники с номерами от LL до RR, узнали результат проверки и настроение каждого из них поделилось на число XX, гарантируется что настроение каждого участника на этом отрезке делится на число XX.

Во всех запросах 1LRN1 \le L \le R \le N.

Формат входного файла

В первой строке вводится число NN и MM, количество участников и количество запросов. В следующих MM строках описываются запросы

Формат выходного файла

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

Примеры

Вход

5 5
0 1 5 1000000007
1 2 3 6
0 1 5 1000000007
2 2 3 3
0 1 5 1000000007

Выход

1
36
4

Вход

3 5
1 1 3 100
0 1 2 10
2 1 3 100
1 2 3 4
0 1 3 10

Выход

0
6