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").