Радость информатика
В этом году на олимпиаде по информатике участвуют 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 строках описываются запросы. Известно, что во всех запросах 1 ≤ L ≤ R ≤ n, 1 ≤ X ≤ 100, 1 ≤ P ≤ 10^9, 1 ≤ n, m ≤ 50000.
Выходные данные
Для каждого запроса типа 0, вывести ответ в отдельной строке.