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.