题目背景

@葛军 改编的水题

题目描述

rainheavy在纸上画了N个点（从1到N编号），每个点的颜色用一个整数描述。rainheavy决定用这N个点随机生成一棵树，生成的规则如下：

对于2号点到N号点，每个点随机指定连接一个点。i号点(2 <= i <= N)的连的点在i的约数中和i的倍数中不超过N的中随机挑选一个。（例如N=30时10号点的可以连接1号，2号，5号，20号，30号）

生成的树中不能有重边（不然就不叫树了）

树生成完之后，rainheavy可以计算出这个树有多少个联通块，一个联通块是一些点的集合，需要满足以下两个条件：

1、从集合中任取两个点都满足：两个点颜色相同，且这两个点之间存在一条树边组成的路径，路径上的所有点都和这两个点颜色相同

2、对于集合中的任意一个点和集合外的任意一个点：两点要么不同色，要么不存在一条树边组成的路径使得路径上所有点都和这两个点同色。

rainheavy希望计算出生成的树中联通块个数最多时，需要连接哪些边，但是rainheavy太强了，不屑于做这种辣鸡题目，更重要的是他要去AK IOI，于是就把题目扔给了你

注：边的顺序

1.首先，满足连通块个数最多的优先（即对于生成连通块有贡献的优先）

2.同样满足条件1时，连接的两个点编号之和较小的边优先（如满足条件1时，连接3号点和5号点的边比连接4号点和5号点的边优先）

3.同时满足条件2时，连接的两个点编号的之中较小的一个较小的边优先（如满足条件2时，连接2号点和6号点的边比连接3号点和5号点的边优先）

输入格式

第一行一个整数N代表点数

第二行N个整数，第i个整数$c_i$代表第i个点的颜色

输出格式

输出共n-1行，每行两个整数x,y表示需要一条边连接点x和点y（要求x<y，且输出的顺序满足题目描述中边的顺序）

Tip：由于输出较多，建议用快速输出（不会就算了顶多T掉嘛对不对）

4
3 2 3 2

1 2
1 4
1 3

提示

对于样例的解释：因为2号、4号点会对生成联通块有贡献（3号你连了也没用），又因为1+2<1+4，所以1 2比1 4优先输出，最后再输出1 3

对于30%的数据, 2 <= N <= 10

对于60%的数据, 2 <= N <= 5000

对于80%的数据, 2 <= N <= 200000

对于100%的数据, 2 <= N <= 500000，1<=颜色<=1e9（反正多了也没用）