C. Wordy Painting
time limit per test
1.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Shakespeare the Tenth has grown bored of writing plays and sonnets all day and wants to get into painting. However, he feels that painting with color is not very artistic, and instead, he wants to paint with letters.

One day, he finds a $$$N \times N$$$ canvas in his basement and starts his painting career. $$$(0, 0)$$$ is the top-left corner of the canvas, and $$$(N-1, N-1)$$$ is the bottom-right corner. A letter takes up a $$$1 \times 1$$$ region and must be aligned on whole number coordinates. As he begins painting, he realizes that a 3D-like effect can be created by stacking letters on each other. Furthermore, he discovers that some letters look better in a given stack and would like these letters to have a majority (making up strictly more than half of the letters) count, which makes it a beautiful stack.

Shakespeare the Tenth decides to paint conduct $$$Q$$$ painting operations, one at a time. One operation is to paint a letter onto a spot in the canvas, which adds it to the top of its stack. Unfortunately, he is not very good at keeping track of his 3D painting and might also ask you to help him determine whether a stack is beautiful. As an inexperienced painter, he might change his mind a lot; therefore, he might like one letter more than the other for a given stack across different queries. In addition, he might choose to remove the top letter of a stack at any given time. If he decides to remove from a stack that he never began painting, it does not do anything. Can you help Shakespeare the Tenth create his favorite painting?

Input

The first line contains $$$N\ (1 \leq N \leq 100)$$$, $$$Q\ (2 \leq Q \leq 2 \cdot 10^5)$$$, the size of the canvas and the number of queries he will ask/paint respectively.

The next $$$Q$$$ lines contain Shakespeare the Tenth's painting steps, removing step, or queries. Each line starts with an integer, $$$s \in \{0, 1, 2\}$$$. If $$$s = 0$$$, then this is a painting step, if $$$s = 1$$$, then this is a remove step, else (if $$$s = 2$$$) a query.

A painting step is followed by 1 (lowercase English) letter and 2 integers, $$$l, x, y\ (0 \leq x, y \leq N - 1)$$$, representing the letter he is painting and the position where he wants to stack the letter.

A remove step is followed by 2 integers, $$$x, y\ (0 \leq x, y \leq N - 1)$$$, representing the position of stack that he wants to remove from.

A query is followed by 1 letter and 2 integers, $$$l, x, y\ (0 \leq x, y \leq N - 1)$$$, the coordinate of the stack he wants to know is beautiful or not and the letter that he thinks will make the stack beautiful at the moment.

All letters that Shakespeare the Tenth uses are lowercase letters.

Output

For each query, output one line denoting whether the stack is beautiful or not with "yes" for beautiful, and "no" for not beautiful. The output is case insensitive.

Example
Input
2 10
0 a 1 1
0 b 0 1
0 a 1 1
2 a 1 1
0 c 0 0
0 d 0 1
2 b 0 1
2 c 0 0
1 0 1
2 b 0 1
Output
yes
no
yes
yes