Радість інформатика
Цього року на олімпіаді з інформатики беруть участь 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 вивести відповідь в окремому рядку.