E. El Café
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Max and his older brother Min had an unbreakable bond throughout their lives. However, a few years ago, Min moved to the Sombrero Galaxy, where he opened a coffee shop, El Café, and became very successful.

Following his family's passion for coffee, Max applied for a job at his brother's coffee shop. The first stage of the selection process is a simulation of a normal working day, which would be straightforward if not for the unconventional way the café serves its customers.

At El Café, there is only one type of drink, the vainilla helada, which consists of a combination of ALL (yes, all) the available ingredients in the store at that moment. Furthermore, each ingredient must be equally distributed among the ordered drinks, based on the quantity of each. Thus, when a customer places an order at El Café, they only specify the number of vainillas heladas they want, and, if possible, the employee must prepare the order. If it is not possible, the customer should be informed that the requested quantity of drinks cannot be made at that time.

For example, if the current list of ingredient quantities is $$$[24, 12, 3]$$$ and a customer orders $$$3$$$ vainillas heladas, Max should inform them that he can fulfill the order, as he can prepare three drinks, each using ingredient quantities $$$[8, 4, 1]$$$. On the other hand, if the customer had requested 2 drinks, Max would have had to inform them that it is not possible at the moment.

During the shift, new ingredients may arrive, and some of the newest ingredients may expire, forcing Max to throw them away (expiration works differently in the Sombrero Galaxy).

To increase his chances of getting the job, Max decides to call you (since he knows your programming skills) and asks you to write a program to help him train for the selection process.

The program must handle $$$3$$$ types of requests:

  • Type $$$1$$$: indicates that a new ingredient has arrived in quantity $$$G$$$. Note that each arriving ingredient is different from the others.
  • Type $$$2$$$: indicates that the last $$$K$$$ ingredients, i.e., the $$$K$$$ newest ingredients, have expired and must be discarded.
  • Type $$$3$$$: simulates a possible order of $$$X$$$ vainillas heladas from a customer. The program should only inform whether it is possible to fulfill such an order.

Given the number $$$N$$$ of different ingredients at the beginning of the shift, the quantity $$$a_i$$$ of each ingredient, and the $$$Q$$$ requests, write a program to help Max pass the test.

Input

The first line consists of two integers $$$N$$$ and $$$Q$$$ $$$(1 \le N, Q \le 10^{5})$$$, representing the number of ingredients at the start of the shift and the number of requests, respectively.

The second line contains $$$N$$$ integers $$$a_1, a_2, \cdots, a_N$$$ $$$(1 \le a_i \le 10^9)$$$, where $$$a_i$$$ represents the quantity of the $$$i$$$-th ingredient in order from oldest to newest.

Then, $$$Q$$$ lines follow, each representing a request.

  • $$$1$$$ $$$G$$$: a type $$$1$$$ request indicating that a new ingredient has arrived in quantity $$$G$$$ $$$(1 \le G \le 10^{9})$$$.
  • $$$2$$$ $$$K$$$: a type $$$2$$$ request indicating that the last $$$K$$$ $$$(1 \le K \le 10^{5})$$$ newest ingredients have expired and should be discarded. It is guaranteed that there will be at least $$$K+1$$$ different ingredients for this type of request.
  • $$$3$$$ $$$X$$$: a type $$$3$$$ request asking whether it is possible to serve $$$X$$$ $$$(1 \le X \le 10^{9})$$$ vainillas heladas at that moment.
Output

For each request of type $$$3$$$, print a single line. If it is possible to fulfill the customer's order, print "SIM", otherwise print "NAO".

Examples
Input
5 5
12 12 6 4 2
2 3
3 4
1 6
1 3
3 2
Output
SIM
NAO
Input
3 3
20 20 4
3 5
1 10
3 2
Output
NAO
SIM