Description

Haru city recently is preparing to between n important landmark building railways, urban railway condition is not complicated, we can build a subway in between any two landmark orbit, but the track is not the more the better, if one of the landmarks in too many metro rail, where the underlying congestion degree drop dramatically increased. Therefore, the mayor decides to give each landmark a convenience degree to measure the degree of congestion. If there are, if there are $$k$$ subway tracks passing a landmark, then the convenience degree of the landmark is $$f(d)$$ $$mod$$ $59393$, where $f(x)=\sum^{k}_{i=0} a_ix^i$ is a polynomial of degree $K$ designated by the mayor.

There are costs to building a subway, and the mayor wants as few new tracks as possible, but any two landmarks need to be accessible to each other by subway. The mayor wanted to know what would maximize the sum of the landmarks under the given conditions.

Input Format

Input of the first line contains two positive integers $n$ and $k$, represent the total number of landmarks cola mayor and City polynomial specified landmark is numbered in sequence $1$ to $n$ , ensure data $n\le 3000$ and $k \leq 10$.

The second input line contains $k + 1$ non-negative integer $a_0$ ~ $a_k$, the coefficients of the polynomial mayor specified, all data is guaranteed $a_i \le 50$

Output Format

Output consists of several rows, the first line contains two positive integers separated by a space $m$ and $S$ , respectively, the number of your program in the construction of Metro Rail and the final degree of convenience and.

The next $m$ line, each line contains two space-separated positive integers $u$ and $v$ represents the $u$ and the $v$ between the two landmarks in the construction of a metro rail.

This question will use Special Judge. If there are multiple solutions to maximize the sum of the convenience of landmarks, just 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