Problem description

Prezes firmy Januszex S.A., w czasie wolnym od nawału zleceń, grywa ze swoim synem w szachy. Jak to na Pana Prezesa przystało, zawsze po zakończeniu rozgrywki robi analizę swoich działań, z której to ostatnio wyszło, że atak hetmanami ma duży potencjał. Ponieważ Pan Prezes nie potrafi szybko liczyć, potrzebuje on pomocy w określeniu, ile pól szachują jego poszczególne hetmany rozstawione na planszy. Wiadomo, że Pan Prezes będzie kolejno pytał o każdego hetmana niezależnie od pozostałych.

Pola na kwadratowej szachownicy N × N są określane parą liczb (x,y) oznaczających odpowiednio numer wiersza i kolumny. Są one numerowane kolejnymi liczbami naturalnymi od 0 do N − 1 włącznie.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N oraz Q, oddzielone pojedynczym odstępem i określające kolejno: długość boku szachownicy oraz liczbę zapytań o poszczególne hetmany. W kolejnych Q wierszach znajdują się zapytania o kolejne hetmany, każde w postaci dwóch liczb naturalnych x oraz y, oddzielonych pojedynczym odstępem i oznaczających pole, na którym stoi hetman.

Wyjście

Twój program powinien wypisać na wyjście dokładnie Q wierszy, w i-tym wierszu powinna się znaleźć jedna liczba naturalna – liczba pól, które szachuje i-ty hetman Pana Prezesa włącznie z polem na którym ów hetman stoi.

Ograniczenia

1 ≤ N ≤ 10⁹, 1 ≤ Q ≤ 500 000, 0 ≤ x, y < N.

Przykład

5 2
2 2
0 3

17
13