给定 n，定义递增有理数序列 {a} 为所有满足如下性质的 p/q

• 0<p<q<=n
• gcd(p,q)=1

多次询问，求序列的第 m 项 $a_m$

输入格式

第一行：两个个正整数 n,q，n 的含义见题目描述，q 表示询问次数。

输出格式

共 q 行：每行两个整数，依次为 $a_m$ 的分子和分母。

样例 1 输入

5 9
1 2 3 4 5 6 7 8 9

样例 1 输出

1 5
1 4
1 3
2 5
1 2
3 5
2 3
3 4
4 5

数据范围

n <= 2000000000,q<=10,m <= $\sum_{2 \le i \le n} φ(i)$