Description

Maintain a sequence of length $n$, initially all $0$, supporting the following two operations:

1. U k a: set the $k$-th number in the sequence to $a$.
2. Z c s: on this sequence, each time choose $c$ positive numbers and subtract $1$ from each; ask whether it is possible to perform $s$ such operations.

Each query is independent, i.e., each query does not modify the sequence.

Input Format

The first line contains two positive integers $n, m$, denoting the length of the sequence and the number of operations.

The next $m$ lines contain the $m$ operations.

Output Format

Output several lines. For each Z query, print TAK if it is possible; otherwise, print NIE.

3 8
U 1 5
U 2 7
Z 2 6
U 3 1
Z 2 6
U 2 2
Z 2 6
Z 2 1

NIE
TAK
NIE
TAK

Hint

Constraints

For $100\%$ of the testdata, $1\leq n,m\leq 10^6$, $1\leq k,c\leq n$, $0\leq a\leq 10^9$, $1\leq s\leq 10^9$.

Original title: Logistyka.

Translated by ChatGPT 5