题目背景

勾股数，又名毕氏三元数 。勾股数就是可以构成一个直角三角形三边的一组正整数。

由上可知对于正整数 $x,y,z$，如果 $x^2+y^2=z^2$，那么 $x,y,z$ 就是一组勾股数。

古希腊学者毕达哥拉斯和柏拉图都研究过勾股数并尝试给出计算勾股数的公式，直到古希腊另一位学者丢番图完美解决了这个问题，丢番图找到的构造勾股数的一般法则如下：

若 $a,b$ 是正整数，并且 $2ab$ 是 完全平方数 （开平方结果是整数），令

$$\left\{ \begin{aligned} x & = a+\sqrt{2ab} \\ y & = b+\sqrt{2ab} \\ z & = a+b+\sqrt{2ab} \end{aligned} \right. $$

则 $x,y,z$ 是一组勾股数。

题目描述

给定一个正整数 $N$ ，找到 $z \leq N$ 的所有勾股数。

需要注意的是：

1. $x,y,z$ 和 $y,x,z$ 是同一个勾股数，不能重复计算；
2. 要对找出的所有勾股数进行分类，分类的方法如下：

如果 $x,y,z$ 是一组勾股数，那么 $x,y,z$，$2x,2y,2z$、$3x,3y,3z$、…… 都是同一类勾股数，记这一类勾股数为 $x,y,z$ 类勾股数。输出时需要输出 $x,y,z$ 这一类名以及这一类勾股数的数量。

例如 $3,4,5$、$6,8,10$、$9,12,15$、$12,16,20$ 都是 $3,4,5$ 类勾股数。

输入格式

一个正整数$N$。

输出格式

若干行；

第一行是 $2$ 个正整数 $n,m$，分别表示找到的所有勾股数分类后的类数和所有勾股数的数量；

接下来有 $n$ 行，每行有 $4$ 个整数，前 $3$ 个整数 $x,y,z$ 表示一类勾股数（输出时保证 $x < y$），最后一个整数表示这一类中所有勾股数的数量。

需要注意的是：这 $n$ 类勾股数输出时按照勾股数的 $z$ 升序排序，如果 $z$ 相等，那么按照 $x$ 升序排序。

输入输出样例

100

16 52
3 4 5 20
5 12 13 7
8 15 17 5
7 24 25 4
20 21 29 3
12 35 37 2
9 40 41 2
28 45 53 1
11 60 61 1
16 63 65 1
33 56 65 1
48 55 73 1
13 84 85 1
36 77 85 1
39 80 89 1
65 72 97 1

说明/提示

👀️ 对于$100\%$的数据，$5 \leq N \leq 10000$，勾股数类数 $n \leq 2000$，勾股数总数 $m \leq 15000$。