Республиканская олимпиада по информатике 2014 год, Усть-Каменогорск

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

Ограничение по времени:

3 секунды

Ограничение по памяти:

256 мегабайт

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

Замечание

В 10\% тестов, $1 \le X \le 100$, $P = 10^9+7$, $1 \le N \le 5000$, $1 \le M \le 5000$, нет запросов типа 2 (поделить на $x$) В 45\% тестов, $1 \le X \le 100$, $P = 10^9+7$, $1 \le N \le 5000$, $1 \le M \le 5000$ В 100\% тестов, $1 \le X \le 100$, $1 \le P \le 10^9$, $1 \le N \le 50000$, $1 \le M \le 50000$