Description

An arithmetic progression is a sequence that can be written as $a, a+b, a+2b, \dots ,a+nb\space (n \in \mathbb N)$.

In this problem, $a$ is a non-negative integer and $b$ is a positive integer. Write a program to find arithmetic progressions of length $n$ within the set of bisquares:

$$\{ x | x = p^2 + q^2 \wedge p,q \in \mathbb N \cap [0,m]\}$$

Input Format

The first line contains a positive integer $n$, the required length of the progression. The second line contains a non-negative integer $m$, the upper bound for $p, q$.

Output Format

If no progression is found, output NONE.

If found, output one or more lines, each containing two integers: $a, b$.

These lines should be sorted in ascending order by $b$ as the primary key and by $a$ as the secondary key.

There will be no more than 10,000 such arithmetic progressions.

5
7

1 4
37 4
2 8
29 8
1 12
5 12
13 12
17 12
5 20
2 24

Hint

Constraints For 100% of the testdata, $3 \le n \le 25$, $0 \le m \le 250$.

Problem translation from NOCOW.

USACO Training Section 1.4.

Translated by ChatGPT 5