Let's define the cover time of a graph G with n vertices (numbered 0 through \(n-1\)) as the expected value of the length of a random walk that starts in vertex 0 and stops immediately after visiting each vertex at least once. In other words, the following algorithm is performed:

define current vertex v; initially \(v=0\)
define the set of visited vertices S; initially \(S = \left\lbrace 0 \right\rbrace\)
while S does not contain all vertices:
- select an edge e randomly uniformly among all edges incident on v
- denote the other endpoint of e (different from v) as u
- u becomes the current vertex v and it's added to the set S

The length of this walk is the number of times the last step is performed plus one (equal to the number of visited vertices).

You are given two integers \(n,k\) and a sequence of n integers \(d_0, d_1, \ldots, d_{n-1}\). Construct an undirected graph G with n vertices such that for each \(0 \le i \lt n\), vertex i has degree equal to \(d_i\). The cover time of this graph should be as close to k as possible.

The resulting graph has to be connected. The graph must not contain loops (i.e. edges from a vertex to itself), but it may contain multiple edges between the same pair of vertices.

Constraints

\( 1 \leq n \leq 100 \)
\( 1 \leq d_i \leq n \) for each \(0 \le i \lt n\)
\(\sum\limits_{i=0}^{n-1} d_i \) is even
\( n \leq k \leq n \cdot \sum\limits_{i=0}^{n-1} d_i \)
it's guaranteed that at least one connected graph with n vertices and the given degree sequence exists

Input format

On the first line of the input, there is a single integer n.

On the second line, there are n space-separated integers \(d_0, d_1, \ldots, d_{n-1}\).

On the third line, there is a single integer k.

Output format

On the first line, print one integer m denoting the number of edges in the graph.

Then, print m lines. On the i-th of these lines, print two space-separated integers \(u_i\) and \(v_i\) (\(0 \leq u_i, v_i \lt n\)) denoting an edge between vertices \(u_i\) and \(v_i\) in the graph.

Test case generation

Each test file has manually assigned values of n and a range \([A, B]\). A sequence \(f_0, f_1, \ldots, f_{n-1}\) will be drawn randomly independently from the uniform integer distribution over the range \([A, B]\). Next, the sequence \(d_0, d_1, \ldots, d_{n-1}\) is generated from \(f_0, f_1, \ldots, f_{n-1}\) using the expected_degree_graph function (without self-loops) from the Python networkx module.

The value of k is chosen in the following way: Several random walks in graphs are generated; let's denote the length of the shortest and longest walk by \(l_{min}\) and \(l_{max}\) respectively. Then, k is chosen randomly uniformly from the range \([l_{min}, l_{max}]\).

Scoring

For each test file, the checker will take the graph generated by your program, run the random walk algorithm described at the beginning of the problem statement \(W=25000\) times and compute the average of their lengths; let's denote this average by X. This value will be used as an approximation of the cover time of the graph. The random walks will be generated using a fixed seed for each test file.

If \(X \ge 10k\), the verdict of your submission for the given test file will be Wrong Answer. Otherwise, the score of your submission will be \((X-k)^2 / k\).

During the contest, every submission will be evaluated on \(50\) test files. The total score for a submission is the sum of the scores for all test files. The goal is to minimize the total score.

After the contest, every submission will be re-evaluated on \(100\) test files. This set will be generated using the method described above in the following way: for each test with parameters \(n, A, B\) in the test set used during the contest, two tests with the same parameters \(n, A, B\) (but not necessarily the same seed) will appear in this final test set. The final score of your solution will be its total score on these \(100\) test files.