You are playing a variation on the chess game on board with N×N squares. Rows and columns are numbered from 1 to N. You also have Q queens. Let us remind that the queen is a piece in chess that can move any number of squares horizontally, vertically, or diagonally.
You will be placing the queens on the board. The only condition is that no two queens can attack each other. Before each placement, you have to determine if placing a queen in this particular place is safe from the already placed queens. If the place is not safe, you don't put the queen at that place and just continue checking new positions.
Input The first line contains two integers N and Q (1≤N,Q≤100000), the size of the board and the number of queries respectively.
The next Q lines contain two integers Xi and Yi (1≤Xi,Yi≤N) – the position where we want to place the queen. We will never try to put a queen at the same place that we already tried to put a queen before, so all pairs (Xi,Yi) will be different.
Output For i-th query, output YES if placing the i-th queen was successful (it didn't cause any two queens attacking each other) or NO otherwise.\
((the question is form eerichto's bootcamp " queens attack").
Make four arrays. Two of them will be row[n] and col[n]. row[i] will tell you whether there is a queen currently in the ith row. Same for col. Two more arrays for diagonals. Notice that on a diagonal, either one of (i+j) is constant or (i-j) is constant. So when you place a queen on square (i,j), set row[i], col[j], diag1[i+j] and diag2[i-j+offset] to true. Choose a value of offset such that i-j+offset is always non-negative.