#64 연속합과 쿼리

Statement

There is a sequence $A=[A_1,A_2,\cdots,A_N]$ of length $N$ . The values of some elements are determined, and the values of some elements are not yet determined.

In the input, elements whose values are not determined are given as $-1$ . Elements whose values are determined are given as integers between $1$ and $10^9$ , inclusive.

You can assign any integer to the undetermined elements. Note that there is no restriction on the range of the integers you can assign.

Given an integer $R$ , you want to know if it is possible to fill in the values of the undetermined elements so that the sequence satisfies the following condition.

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

The above equation must hold for all $1 \le i \le N-R+1$ .

However, the sequence continuously changes due to queries. A query is one of the following two types.

$1\ i\ x$ : Set the value of $A_i$ to $x$ . $(1 \le x \le 10^9)$
$2\ i$ : Change the value of $A_i$ to an undetermined state.

Immediately after each query is performed, determine whether it is possible to appropriately fill in the undetermined elements to satisfy the above condition.

Input

The input is given in the following format.

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

If $A_i=-1$ , it means the value of $A_i$ is not determined. If $A_i\ne -1$ , it means the value of $A_i$ is determined.

The format of each $\rm{query}_i$ $\ (1\le i\le Q)$ is one of the following two.

$1\ i\ x$

$2\ i$

Output

For each query, print YES if it is possible to satisfy the condition immediately after performing the query, and NO otherwise, one per line.

The output is case-insensitive. For example, printing YeS or yes instead of YES does not affect your score.

Constraints

$1 \le N \le 200\ 000$ .
$1 \le R \le N$ .
$-10^{18} \le K \le 10^{18}$ .
$1 \le Q \le 200\ 000$ .
In the initial sequence, each $A_i$ is $-1$ or an integer between $1$ and $10^9$ , inclusive.
In query $1\ i\ x$ , $1 \le i \le N$ , $1 \le x \le 10^9$ .
In query $2\ i$ , $1 \le i \le N$ .

Subtasks

#	점수	제한
1	8	$R=1$ .
2	13	$R=N$ .
3	17	All elements of the initial sequence are undetermined, all queries are in the form of $1\ i\ x$ , and the same index does not appear more than once.
4	24	$N \leq 2 \ 000, \ Q \leq 2 \ 000$ .
5	38	No additional constraints.

Samples

입력

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

출력

YES
NO
YES
NO
YES

After the first query, the sequence is $[3,2,?,?,?]$ . For example, if you fill in the undetermined values to make it $[3,2,5,3,2]$ , the sum of all contiguous subarrays of length $3$ is $10$ , so the answer is YES.