Dat je niz ~A~ sa ~N~ elemenata. ~A_i~ označava ~i~-ti element niza ~A~.

Treba obraditi ~Q~ upita koji su jednog od naredna dva tipa:

• Tip ~1~: Upit se sastoji od nenegativnog celog broja ~x~ i dva pozitivna cela broja ~s~ i ~t~. Na svim elementima većim ili jednakim sa ~x~ u nizu ~A~ izvršiti sledeću operaciju: Dodati ~s~ elementima i zatim ih pomnožiti sa ~t~. Tj. element koji je imao vrednost ~v~ (~v \geq x~) nakon operacije ima vrednost ~(v+s) \cdot t~.
• Tip ~2~: Upit se sastoji od nenegativnog celog broja ~x~ i dva pozitivna cela broja ~s~ i ~t~. Na svim elementima manjim ili jednakim sa ~x~ u nizu ~A~ izvršiti sledeću operaciju: Oduzeti ~s~ elementima i zatim ih podeliti sa ~t~. Ukoliko rezultat nije ceo broj, zaokružiti ga na ceo broj bliži nuli. Npr. broj ~3.7~ zaokružiti na ~3~, a broj ~-2.8~ na ~-2~.

Posle primenjivanja svih ovih operacija (jedne po jedne), koliko elemenata postoji u nizu, koji su veći ili jednaki sa ~L~ i manji ili jednaki sa ~R~.

Opis ulaza

Prva linija standardnog ulaza sadrži četiri broja ~N~, ~Q~, ~L~ i ~R~ (~1 \leq N \leq 2 \cdot 10^5~, ~1 \leq Q \leq 2 \cdot 10^5~, ~-2^{63} < L \leq R < 2^{63}~). U narednoj liniji nalazi se ~N~ brojeva, ~i~-ti od njih predstavlja ~A_{i}~ (~|A_{i}| \leq 10^9~). Narednih ~Q~ linija sadrže po četiri broja ~q_{j}~, ~x_{j}~, ~s_{j}~, ~t_{j}~, gde je ~q_{j} = 1~, ukoliko je dat upit prvog tipa i ~q_{j} = 2~, ukoliko je dat upit drugog tipa (~0 \leq x < 2^{63}~, ~1 \leq s_{j},t_{j} \leq 10^9~). Apsolutna vrednost svakog elementa niza je strogo manja od ~2^{63}~ u toku bilo kog trenutka obrađivanja upita.

Opis izlaza

U prvoj i jedinoj liniji standardnog izlaza ispisati koliko elemenata u nizu ~A~ je veće ili jednako sa ~L~ i manje ili jednako sa ~R~.

Primer ulaza

3 3 3 10
1 -2 3
1 2 2 3
2 20 1 3
2 1 20 5

Primer izlaza

1