题目描述

经过选拔，Kiana成为了可乐城的市长，为了兑现选举承诺，她决定在可乐城的 $n$ 个重要地标之间修建地铁。

可乐城的交通状况并不复杂，在任意两个地标之间修建一条地铁轨道都是可行的，但是地铁轨道并不是越多越好，如果有太多地铁从一个地标处经过，该地标的拥堵程度将大幅增加。为此，Kiana决定给每个地标一个便利度来衡量拥堵程度，如果有 $d$ 条地铁轨道经过了某个地标，那么该地标的便利度为 $f(d)\mod 59393$，其中 $f(x)=\sum_{i=0}^{k}a_ix^i$ 是Kiana指定的一个 $k$ 次多项式。

因为修建地铁有一定的成本，所以Kiana希望新建的地铁轨道尽可能少，但任意两座地标之间都需要能通过地铁相互到达。Kiana想知道在给定的条件下，什么样的修建方案可以使得地标的便利度之和最大。由于她不会做，所以希望你来告诉她答案。

输入格式

输入第一行包含两个正整数 $n$ 和 $k$，分别表示可乐城的地标总数和Kiana指定的多项式次数，地标的编号依次为 $1$ 至 $n$，数据保证 $n\leq 3000$且 $k\leq 10$。

输入第二行包含 $k+1$ 个非负整数 $a_0\sim a_k$，即Kiana指定的多项式的系数，数据保证所有的 $a_i\leq 50$。

输出格式

输出由若干行组成，第一行包含两个用空格隔开的正整数 $m$ 和 $S$，分别表示你的方案中修建的地铁轨道数量与最终的便利度之和。

接下来 $m$ 行，每行包含两个用空格隔开的正整数 $u$ 和 $v$，表示在第 $u$ 和第 $v$ 个地标之间修建了一条地铁轨道。

本题将采用Special Judge，如果有多种方案使得地标的便利度之和最大，输出其中任意一种即可。

4 2
0 0 1

3 12
1 2
1 3
1 4

10 9
10 9 8 7 6 5 4 3 2 1

9 177454
4 5
4 6
3 4
3 7
2 3
2 8
1 2
1 9
1 10

提示

备注

本题因为一些原因只保留了后 $50$ 组数据。

版权信息

来自 2018 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2018），感谢 Pony.ai 对此次比赛的支持。

题解等资源可在 https://github.com/wangyurzee7/THUPC2018 查看。