Sequence Operations: Update and Subtraction Query

You are given a sequence of length \( n \) (1-indexed) where initially every element is 0. The sequence supports two types of operations:

1. U k a: Update the \( k \)th element of the sequence to \( a \) (i.e. set \( a_k = a \)).
2. Z c s: Query whether it is possible to perform \( s \) operations on the current sequence. In each operation, you must choose \( c \) distinct indices such that the corresponding elements are positive, and subtract 1 from each of them. This query is independent (i.e. the sequence is not modified by the query).

Note: An index can be chosen at most once during each operation. Hence, even if an element is large, it can contribute at most 1 to each operation, and overall at most \( s \) times across \( s \) operations. A necessary and sufficient condition for the query to be successful is: \[ \sum_{i=1}^{n} \min(a_i, s) \geq s \times c. \]

For each query of type Z, output 1 if it is possible to complete the \( s \) operations, or 0 otherwise.

inputFormat

The first line contains two integers \( n \) and \( q \) (the length of the sequence and the number of queries).

Each of the following \( q \) lines describes an operation in one of the following formats:

• U k a — update the \( k \)th element of the sequence to \( a \).
• Z c s — query if it is possible to perform \( s \) operations, where in each operation you choose \( c \) distinct indices having a positive value and subtract 1 from each.

It is guaranteed that all input values are valid and that \( 1 \leq k \leq n \).

outputFormat

For each query of type Z, output a single line containing 1 if it is possible to perform the \( s \) operations, or 0 otherwise.

sample

5 5
U 1 3
U 3 2
Z 2 2
U 2 1
Z 3 1

1
1