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