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

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

В этом году на олимпиаде по информатике участвуют $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$.

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

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

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

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

Для каждого запроса типа 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