Problem Description

After being selected, Kiana has become the mayor of Cola City. To fulfill her campaign promises, she decides to build a subway system connecting \( n \) important landmarks in Cola City.

The traffic situation in Cola City is not complex; it is feasible to build a subway track between any two landmarks. However, having too many subway tracks passing through a landmark can significantly increase its congestion. Therefore, Kiana decides to assign a convenience value to each landmark to measure its congestion. If \( d \) subway tracks pass through a landmark, its convenience value is \( f(d) \mod 59393 \), where \( f(x) = \sum_{i=0}^{k} a_i x^i \) is a polynomial of degree \( k \) specified by Kiana.

Since building subways incurs costs, Kiana wants to build as few subway tracks as possible while ensuring that any two landmarks can be reached via the subway system. Kiana wants to know under the given conditions, what construction plan can maximize the sum of the convenience values of the landmarks. Since she doesn't know how to solve this, she hopes you can tell her the answer.

Input Format

The first line of input contains two positive integers \( n \) and \( k \), representing the total number of landmarks in Cola City and the degree of the polynomial specified by Kiana, respectively. The landmarks are numbered from 1 to \( n \). The data guarantees \( n \leq 3000 \) and \( k \leq 10 \).

The second line contains \( k+1 \) non-negative integers \( a_0 \) to \( a_k \), which are the coefficients of the polynomial specified by Kiana. The data guarantees that all \( a_i \leq 50 \).

Output Format

The output consists of several lines. The first line contains two positive integers \( m \) and \( S \), separated by a space, representing the number of subway tracks built in your plan and the final sum of convenience values, respectively.

The next \( m \) lines each contain two positive integers \( u \) and \( v \), separated by a space, indicating that a subway track is built between the \( u \)-th and \( v \)-th landmarks.

This problem will use a Special Judge. If there are multiple plans that maximize the sum of convenience values, any one of them can be output.

Sample Input and Output

Sample Input #1

4 2
0 0 1

Sample Output #1

3 12
1 2
1 3
1 4

Sample Input #2

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

Sample Output #2

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

Notes

Remarks

Due to certain reasons, only the last 50 sets of data are retained.

Copyright Information

This problem is from the 2018 Tsinghua University Student Programming Contest and University Invitational (THUPC2018). Thanks to Pony.ai for their support of this competition.

Solutions and other resources can be found at https://github.com/wangyurzee7/THUPC2018.

见题面 Input 部分

见题面 Output 部分