В этом году на олимпиаде по информатике участвуют 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 ≤ 109, 1 ≤ n, m ≤ 50000.

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

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