İnformatikanın sevinci

Bu il informatika olimpiadasında n şagird iştirak edir. İştirakçılar 1-dən n-ə qədər nömrələniblər.

Yeni sistemə əsasən, onlar tapşırığın həllini göndərdikdən dərhal sonra öz ballarını görə bilirlər. Yoxlama nəticəsinə görə, iştirakçının əhval-ruhiyyəsi əhəmiyyətli dərəcədə dəyişə bilər. Olimpiadanın əvvəlində bütün iştirakçıların əhval-ruhiyyəsi birdir.

İştirakçıların əhval-ruhiyyə dəyişikliklərinin tarixi var. Münsiflər heyəti bütün iştirakçıların əhval-ruhiyyəsini izləmək istəyir və sizdən kömək istəyir.

Sizin üç növ sorğunuz var:

0 L R P - Münsiflər heyəti L-dən R-ə qədər nömrələnmiş bütün iştirakçıların əhval-ruhiyyələrinin hasilini bilmək istəyir. Lakin bu ədəd çox böyük ola biləcəyi üçün onu P modulunda çıxarmaq lazımdır;

1 L R X - L-dən R-ə qədər nömrələnmiş bütün iştirakçılar yoxlama nəticəsini öyrəndilər və hər birinin əhval-ruhiyyəsi X ədədinə vuruldu;

2 L R X - L-dən R-ə qədər nömrələnmiş bütün iştirakçılar yoxlama nəticəsini öyrəndilər və hər birinin əhval-ruhiyyəsi X ədədinə bölündü, bu aralıqdakı hər bir iştirakçının əhval-ruhiyyəsinin X ədədinə bölündüyü təmin edilir.

Giriş məlumatları

Birinci sətirdə n və m ədədləri, iştirakçıların sayı və sorğuların sayı verilir. Növbəti m sətirdə sorğular təsvir olunur. Bütün sorğularda 1 ≤ L ≤ R ≤ n, 1 ≤ X ≤ 100, 1 ≤ P ≤ 10^9, 1 ≤ n, m ≤ 50000 olduğu məlumdur.

Çıxış məlumatları

Hər bir 0 tipli sorğu üçün cavabı ayrı sətirdə çıxarmaq lazımdır.