CSES - Datatähti 2022 alku - Spiraali (Spiral)
  • Time limit: 1.00 s
  • Memory limit: 512 MB
Tarkastellaan $n \times n$ -kokoista spiraalia, joka sisältää luvut $1 \dots n^2$ aloittaen vasemmasta yläkulmasta ja kiertäen vastapäivään. Tämän tehtävän oletuksena on, että $n$ on aina parillinen.

Esimerkiksi tapauksessa $n=6$ spiraali näyttää tältä:

Tehtäväsi on selvittää tehokkaasti tietyssä kohdassa spiraalia oleva luku.

Syöte

Syötteen ensimmäisellä rivillä on kaksi lukua $n$ ja $t$: spiraalin koko ja testien määrä.

Tämän jälkeen syötteessä on $t$ riviä, joista jokainen kuvaa yhden testin. Rivillä on kaksi kokonaislukua $y$ ja $x$: rivi ja sarake.

Tuloste

Tulosta jokaisesta testistä rivillä $y$ sarakkeessa $x$ oleva luku.

Esimerkki

Syöte:
6 5
1 1
2 5
4 2
4 4
5 6


Tuloste:
1
30
23
35
12


Osatehtävä 1 (15 pistettä)
  • $n=10$
  • $t=100$
Osatehtävä 2 (20 pistettä)
  • $n=1000$
  • $t=1000$
Osatehtävä 3 (65 pistettä)
  • $n=10^9$
  • $t=1000$


Consider an $n \times n$ sized spiral that contains the numbers $1 \dots n^2$, starting from the top left corner and continuing in counterclockwise order. For the purposes of this task, we assume that $n$ is always even.

For example, in the case $n=6$ the spiral looks like this:

Your task is to efficiently report the number at a specific location in the spiral.

Input

The first line of input contains the integers $n$ and $t$: the size of the spiral and the number of tests.

The following $t$ lines each describe one test. The lines contain two integers, $y$ and $x$, denoting the row and column.

Output

For each test, print the number at row $y$ and column $x$ of the spiral.

Example

Input:
6 5
1 1
2 5
4 2
4 4
5 6


Output:
1
30
23
35
12


Subtask 1 (15 points)
  • $n=10$
  • $t=100$
Subtask 2 (20 points)
  • $n=1000$
  • $t=1000$
Subtask 3 (65 points)
  • $n=10^9$
  • $t=1000$