Description

After being selected, Kiana became the mayor of Kele City. To fulfill her campaign promise, she decided to build a metro system among the $n$ important landmarks in Kele City.

The traffic situation in Kele City is not complicated. It is feasible to build a metro track between any two landmarks. However, more metro tracks are not always better: if too many tracks pass through a landmark, the congestion at that landmark will increase significantly. Therefore, Kiana decided to assign each landmark a convenience value to measure congestion. If $d$ metro tracks pass through a landmark, then its convenience value is $f(d)\mod 59393$, where $f(x)=\sum_{i=0}^{k}a_ix^i$ is a degree-$k$ polynomial specified by Kiana.

Building metro tracks has a cost, so Kiana wants the number of newly built tracks to be as small as possible, while any two landmarks must be able to reach each other by metro. Kiana wants to know, under the given conditions, what construction plan can maximize the sum of convenience values over all landmarks. Since she cannot solve it, she asks you to give her the answer.

Input Format

The first line contains two positive integers $n$ and $k$, representing the total number of landmarks in Kele City and the degree of the polynomial specified by Kiana. The landmarks are numbered from $1$ to $n$. The testdata guarantees $n\leq 3000$ and $k\leq 10$.

The second line contains $k+1$ non-negative integers $a_0\sim a_k$, i.e., the coefficients of the polynomial specified by Kiana. The testdata guarantees that all $a_i\leq 50$.

Output Format

The output consists of multiple lines. The first line contains two positive integers $m$ and $S$ separated by a space, representing the number of metro tracks built in your plan and the final sum of convenience values.

In the next $m$ lines, each line contains two positive integers $u$ and $v$ separated by a space, indicating that a metro track is built between landmark $u$ and landmark $v$.

This problem uses a Special Judge. If multiple plans maximize the sum of convenience values, you may output any one of them.

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

Hint

Notes

Due to some reasons, only the last $50$ groups of testdata are kept for this problem.

Copyright Information

From the 2018 Tsinghua University Programming Contest and Collegiate Invitational (THUPC2018). Thanks to Pony.ai for supporting this contest.

Resources such as solutions can be found at https://github.com/wangyurzee7/THUPC2018.

Translated by ChatGPT 5