Сізге өзара жай екі оң бүтін $p$ және $q$ сандары берілген. $0, 1, \ldots, pq - 1$ сандарымен нөмірленген $pq$ түрлі карта бар.

Стандартты карта бумаларының екі түрі бар:

• 1-түрдегі стандартты карта бумалары: олардың $u$ ($0 \le u < p$) санымен нөмірленген $p$ түрі бар. Нөмірі $u$ болатын бумада нөмірі $x \equiv u \pmod{p}$ шартын қанағаттандыратын әр картаның бір данасы бар, сондықтан әр бумада дәл $q$ карта болады.
• 2-түрдегі стандартты карта бумалары: олардың $v$ ($0 \le v < q$) санымен нөмірленген $q$ түрі бар. Нөмірі $v$ болатын бумада нөмірі $x \equiv v \pmod{q}$ шартын қанағаттандыратын әр картаның бір данасы бар, сондықтан әр бумада дәл $p$ карта болады.

Қазір үстел үстінде $n$ карта қатарға тізіліп тұр, мұндағы $i$-ші картаның нөмірі — $a_i$. Сізге келесі екі түрдегі $Q$ операцияны орындау қажет:

• 1 i x: $i$-ші картаның нөмірін $x$-ке ауыстыру;
• 2 l r: $[l, r]$ аралығындағы барлық карталарды бірнеше стандартты карта бумаларына қалдықсыз дәл бөлуге болатынын анықтау.

Ескертпе: Карталарды қайта бумалаған кезде аралықтағы әрбір карта дәл бір бумаға тиесілі болуы керек, ал стандартты карта бумасының әрбір түрін кез келген рет қолдануға болады.

Кіріс деректер

Бірінші жолда төрт бүтін сан $n, p, q, Q$ ($1 \le n, p, q, Q \le 3 \times 10^5$, $2 \le p + q \le 3 \times 10^5$, $\gcd(p, q) = 1$) берілген.

Екінші жолда әр картаның бастапқы нөмірін білдіретін $n$ бүтін сан $a_1, a_2, \ldots, a_n$ ($0 \le a_i < pq$) берілген.

Келесі $Q$ жолдың әрқайсысы 1 i x немесе 2 l r түріндегі бір операцияны сипаттайды:

• Бірінші түрдегі әрбір операция үшін $1 \le i \le n$ және $0 \le x < pq$ екеніне кепілдік беріледі.
• Екінші түрдегі әрбір операция үшін $1 \le l \le r \le n$ екеніне кепілдік беріледі.

Шығыс деректер

Екінші түрдегі әрбір операция үшін көрсетілген карталарды бірнеше стандартты карта бумаларына дәл бөлуге болса, YES деп, әйтпесе NO деп шығарыңыз.

Мысалдар

Кіріс деректер 1

8 2 3 5
0 0 2 3 4 1 4 2
2 1 5
2 6 8
1 8 5
2 6 8
2 6 7

Шығыс деректер 1

YES
NO
NO
YES

Ескертпе

$p = 2, q = 3$ болғанда:

• 1-түрдегі екі стандартты карта бумасы бар: $\{0, 2, 4\}$ және $\{1, 3, 5\}$.
• 2-түрдегі үш стандартты карта бумасы бар: $\{0, 3\}$, $\{1, 4\}$ және $\{2, 5\}$.

Бірінші сұраныс үшін аралықтағы карталардың мультижиыны — $\{0, 0, 2, 3, 4\}$. Оны $\{0, 2, 4\} + \{0, 3\}$ түрінде бөлуге болады, сондықтан жауабы — YES.

Соңғы сұраныс үшін аралықтағы карталардың мультижиыны — $\{1, 4\}$. Ол дәл бір 2-түрдегі стандартты карта бумасын құрайды, сондықтан жауабы — YES.