M. Mirage of the Waterfalls
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

An ancient legend from Foz do Iguaçu tells of a rare mirage that forms in the Devil's Throat: for a single, fleeting moment, a horizontal trail of barrels appears in the middle of the water curtain. Maria, a fearless acrobat, is determined to become the first to cross this trail before it disappears.

For the crossing, the waterfall is modeled as a line of $$$N$$$ positions for barrels, numbered from $$$0$$$ to $$$N-1$$$. Maria starts from the shore at position $$$-1$$$ and her goal is to reach the opposite shore at position $$$N$$$. Her jumping ability is $$$K$$$, which means she can jump from a foothold $$$i$$$ to a barrel $$$j$$$ if $$$(j-i) \le K$$$. Naturally, she can only land on barrels that are available in the mirage.

The biggest challenge is the chaotic nature of the waterfall, which changes the configuration of the barrels. Your task is to analyze $$$Q$$$ of these events and determine, for the initial configuration and after each change, whether Maria can cross the waterfall.

Input

The first line of the input contains three integers separated by spaces: $$$N$$$, $$$Q$$$, and $$$K$$$ ($$$1 \le N, Q \le 2 \times 10^{5}$$$, $$$1 \le K \le 10^{9}$$$), representing the number of barrels, the number of events, and Maria's jumping ability, respectively. The second line contains $$$N$$$ integers, $$$a_1, a_2, \ldots, a_{N}$$$, where $$$a_i = 1$$$ if the $$$i$$$-th barrel is initially usable, and $$$a_i = 0$$$ if it is broken.

The next $$$Q$$$ lines describe the events. Each line contains three integers $$$T$$$ ($$$1 \le T \le 2$$$), $$$L$$$ and $$$R$$$ ($$$1 \le L \le R \le N$$$).

  • If $$$T = 1$$$, the river dumps more barrels into the waterfall. In the range of positions $$$[L, R]$$$, all barrels become available.
  • If $$$T = 2$$$, a strong current sweeps the barrels away. In the range of positions $$$[L, R]$$$, all barrels become unavailable.
Output

The output should contain $$$Q+1$$$ lines, representing the answer for the initial state and all subsequent states. For each answer, print "SIM" if the traversal is possible, and "NAO" otherwise.

Examples
Input
10 3 4
1 1 0 0 0 0 0 0 1 1
1 5 6
2 5 6
1 1 10
Output
NAO
SIM
NAO
SIM
Input
8 2 3
0 0 1 0 0 1 0 0
2 6 6
1 6 7
Output
SIM
NAO
SIM