Faberje yumurtaları Karl Faberje firmasının hazırladığı zərif pasxa yumurtalarının məşhur seriyasıdır. Bu seriyalar \textbf{1885}-ci ildən \textbf{1917}-ci ilə qədər olan dövrdə Rusiya imperator ailəsi və xüsusi sifarişçilər üçün yaradılmışdır. Belə sifarışçilərdən biri Karl Faberjeyə \textbf{n} sayda qiymətli yumurta hazırlamağı sifariş verir. Hər bir yumurta \textbf{m}-dən böyük olmayan sayda zolaqlardan ibarət idi, belə ki, hər zolaqda bir rəngdə olan qiymətli daşlar yerləşirdi. Fəqət kolleksiya oğurlanır. İşə ən yaxşı detektivlər: Şerlok Holms və doktor Vatson cəlb edilir. Bu qiymətli cəvahirat qara bazara düşə bildiyindən, detektivlərin tanıması üçün onların necə göründüklərini bilmələri lazımdır. Vaxta qənaət üçün, sahibi həmin cəvahiratın Şerlok Holmsun nömrəsini dediyi əvvəlki cəvahiratdan nə ilə fərqləndiyini danışdı. Siz cəvahiratlar haqqında informasiyanın saxlanması üçün effektiv struktur yazmalısınız. Onun dəqiqliyinə əmin olmaq üçün həm də aşağıdakı şəkildə olan suallara cavab vermək lazımdır: “Cəvahiratdakı \textit{\textbf{l}}\textit{ və }\textit{\textbf{r}} zolaqları arasında (özləri də daxil olmaqla) neçə müxtəlif rəngli qiymətli daş yerləşir?”. \InputFile Birinci sətirdə iki \textbf{m (1 ≤ m ≤ 100000)} və \textbf{n (1 ≤ n ≤ 50000)} ədədləri yerləşir, burada, \textbf{m} -- qiymətli daşlardan ibarət zolaqların sayı, \textbf{n} -- Faberje yumurtalarının sayıdır. Sonrakı \textbf{k (1 ≤ k ≤ 200000)} sətirdə \textbf{n}\textit{ }qrup verilir. Hər qrup iki \textbf{i (1 ≤ i ≤ n)} və \textbf{k} ədədlərilə başlayır. Burada \textbf{i} -- qrupun nömrəsi, \textbf{k} -- cari məmulatın aşağdakı şəkildə olan \textbf{x} məmulatından məhz nə ilə fərqləndiyini göstərən sorğuların sayıdır: \textbf{l r c} -- \textbf{\[l, r\]} aralığında olan cari cəvahiratın \textbf{с (1 ≤ с ≤ 32)} rəngini müəyyənləşdirmək. Həmçinin, hər qrup aşağıdakı şəkildə sorğu ilə qurtarır: \textbf{l r} -- cari cəvahiratdakı \textbf{\[l, r\]} aralığında müxtəlif rənglərin sayını hesablamaq. \textbf{x}-i hesablamaq üçün aşağıdakı düsturdan istifadə etmək lazımdır: \textbf{x = ( i + v ) mod i}, burada \textbf{v} -- ikinci tipdən olan əvvəlki sorğunun cavabı, \textbf{i} -- cari qrupun nömrəsidir. Başlanğıcda \textbf{v = 0}. Təminat verilir ki, \textbf{1 ≤ l, r ≤ m} şərti ödənilir. \textbf{0} nömrəli cəvahirat zolaqlarında qiymətli daşlar yerləşməyən yumurtadır. Bəzi məmulatlarda hansısa zolaqlar olmaya da bilər. \OutputFile İkinci tipdən olan hər sorğunun cavabını ayrıca sətirdə verin.