서로소인 두 양의 정수 $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입니다.