Now that Inaho knows the direction of the least density, he wants to get out of this horrible ~N~-dimensional hole to return to playing his Graph Simulator 2015. Each unit of density costs him ~1~ year to walk through, and he wants to leave as quickly as possible. Of course, these are ~N~-dimensional years we're talking about, which translates to ~1~ nanosecond in ~3~-dimensional space. As he still cannot understand the complexities of ~N~ dimensions, he asks for your help once again!

Inaho wants you to find the minimum time he needs to travel in order to escape, if he is only able to travel parallel to any axis. He is currently at the position of the greatest density, and would like to get to the position of the least density.

Inaho must wade out of his starting point, and wade into the position of the least density. Therefore the time taken includes the time needed to travel out of the starting point and into the destination point.

Input Specification

The first line will contain the integer ~N~ ~(1 \le N \le 10)~, the number of dimensions.

The second line will contain ~N~ space-separated integers that represent the size of each dimension, ~l_1, l_2, \dots, l_N~ ~(1 \le l_1 \times l_2 \times \dots \times l_N \le 2 \times 10^6)~.

On the third line will contain ~l_1 \times l_2 \times \dots \times l_N~ integers ~(0 \le d_i \le 10^{12})~.

~d_i~ represents the density at position ~p_i~ where ~p_i = \sum\limits_{n=1}^N \left(p_{i_n} \times \prod\limits_{j=n+1}^N l_j\right)~.

In other words, the third line will be a flattened ~N~-dimensional grid.

If there are multiple positions with the least density, Inaho's destination is at the position that occurs the earliest in the input.

If there are multiple positions with the greatest density, Inaho is at the position that occurs the latest in the input.

It is guaranteed that any simple path through this ~N~-dimensional space takes no longer than ~2^{63} - 1~ years.

Output Specification

On the first line, output the minimum amount of time he needs to travel in this ~N~-dimensional hole before he can reach the position of least density.

On the subsequent lines, output the points Inaho must visit to reach the position of least density (including the source and the destination) in order. Each line shall consist of ~N~ ~0~-indexed space separated integers specifying Inaho's position in each dimension.

Printing out any valid simple path with the shortest distance will grant full marks.

For only printing the shortest distance without the path, ~50\%~ of points will be granted.

Subtasks

For 1 of the 17 available marks, ~d_i = 0~.

For an additional 1 of the 17 available marks, ~d_i = 1~.

For an additional 1 of the 17 available marks, ~N \le 2~.

For an additional 2 of the 17 available marks, ~N \le 3~.

For an additional 3 of the 17 available marks, ~N \le 4~.

Sample Input 1

2
5 5
14 4 15 1 7 15 6 9 3 13 13 6 8 13 4 11 11 1 14 10 11 2 15 9 10

Sample Output 1

37
4 2
3 2
2 2
1 2
1 3
0 3

Sample Input 2

2
20 2
10 6 1 13 1 15 2 10 12 3 3 5 10 8 3 1 2 1 6 2 4 6 13 1 3 9 7 15 16 5 4 7 1 16 6 4 6 7 10 5

Sample Output 2

93
16 1
15 1
14 1
13 1
12 1
11 1
10 1
9 1
8 1
7 1
6 1
5 1
4 1
3 1
3 0
2 0
1 0