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

(Информатик қуанышы)

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

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$, екінші типті сұраулар жоқ ($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$