Радість інформатика

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