#64 sumquery

Statement

길이 $N$ 의 수열 $A=[A_1,A_2,\cdots,A_N]$ 이 있다. 일부 원소의 값은 정해져 있고, 일부 원소의 값은 아직 정해져 있지 않다.

입력에서 값이 정해지지 않은 원소는 $-1$ 으로 주어진다. 값이 정해진 원소는 $1$ 이상 $10^9$ 이하의 정수로 주어진다.

정해지지 않은 원소에는 원하는 정수를 넣을 수 있다. 이때 넣는 정수의 범위에는 제한이 없다.

당신은 정수 $R$ 이 주어질 때, 수열이 다음 조건을 만족하도록 정해지지 않은 원소들의 값을 채울 수 있는지 알고 싶다.

$A_i+A_{i+1}+\cdots+A_{i+R-1}=K$

위 식이 모든 $1 \le i \le N-R+1$ 에 대해 성립해야 한다.

하지만 수열은 쿼리에 의해 계속 바뀐다. 쿼리는 다음 두 종류 중 하나이다.

각 쿼리가 수행된 직후, 정해지지 않은 원소들을 적절히 채워 위 조건을 만족하게 만들 수 있는지 판별하여라.

입력은 다음과 같은 형식으로 주어진다.

$N\ R\ K\ Q$ $A_1\ A_2\ \cdots \ A_N$ $\rm{query_1}$ $\rm{query_2}$ $\vdots$ $\rm{query_Q}$

$A_i=-1$ 이면 $A_i$ 의 값이 정해지지 않았다는 뜻이다. $A_i\ne -1$ 이면 $A_i$ 의 값이 정해져 있다는 뜻이다.

각각의 $\rm{query}_i$ $\ (1\le i\le Q)$ 의 형식은 다음 둘 중 하나이다.

$1\ i\ x$

$2\ i$

각 쿼리마다, 쿼리를 수행한 직후 조건을 만족하게 만들 수 있으면 YES, 아니면 NO를 한 줄에 하나씩 출력한다. 대소문자는 구별하지 않는다.

#	Score	Constraints
1	8	$R=1$ .
2	13	$R=N$ .
3	17	초기 수열의 모든 원소가 정해지지 않았고, 모든 쿼리는 $1\ i\ x$ 꼴이며, 같은 인덱스가 두 번 이상 등장하지 않는다.
4	24	$N \leq 2 \ 000, \ Q \leq 2 \ 000$ .
5	38	추가적인 제약 조건이 없다.

Input

3 10 5
-1 2 -1 -1 -1
1 3
4 4
4
3 6
3

Output

YES
NO
YES
NO
YES

첫 번째 쿼리 후 수열은 $[3,2,?,?,?]$ 이다. 예를 들어 정해지지 않은 값을 채워 $[3,2,5,3,2]$ 로 만들면 길이 $3$ 의 모든 연속 구간합이 $10$ 이므로 YES이다.