After analyzing the triple peaks of the Cordillera Oriental, expert topographers (including yourself) have shifted their focus onto the rising sea levels, and their effects on the DMOJistan islands.

The DMOJistan landscape is described as an array of ~N~ integers, ~h_1, h_2, \dots, h_N~, where ~h_i~ denotes the elevation of the ~i^{th}~ patch of land from the left border of DMOJistan. It is known that all elevations ~h_i~ are in the inclusive range ~[0,N]~, and that the patches of land just outside DMOJistan have zero elevation, i.e. ~h_0 = h_{N+1} = 0~.

For a given sea level ~s~, a contiguous segment of land from index ~l~ to ~r~ is called an island if all patches of land within it have elevations greater than or equal to sea level, and the patches of land to its immediate left and right are both below sea level. Formally, for integers ~l~ and ~r~ satisfying ~1 \le l \le r \le N~, the segment of land from index ~l~ to ~r~ is an island if and only if ~h_l, h_{l+1}, \dots, h_r \ge s~ and ~h_{l-1}, h_{r+1} < s~.

Let ~c_i~ denote the number of distinct islands there would be in DMOJistan if the sea level was ~i~.

You will be given an integer ~T \in \{1,2\}~, indicating which of the following subtasks you must solve:

Subtask 1:

The year is 2025, and DMOJistan has not yet been submerged in water. After measuring DMOJistan's elevation data, ~h_1, h_2, \dots, h_N~, you would like to predict how the number of islands will change as sea levels rise. Compute the values of ~c_1, c_2, \dots, c_N~.

Subtask 2:

The year is 3000, and sea levels have risen so high that DMOJistan has become completely submerged. The only remaining info on DMOJistan's landscape are the values of ~c_1, c_2, \dots, c_N~, recorded by a topographer of the past. You must now make an educated guess on what the topography of DMOJistan was long ago based on this data.

Determine any landscape described by ~N~ integer elevations in the range ~[0,N]~, ~h_1, h_2, \dots h_N~, which would have produced the given values of ~c_1, c_2, \dots, c_N~ as sea levels rose. If such a landscape cannot exist, output -1 instead.

Constraints

~T \in \{1,2\}~

~1 \le N \le 2 \times 10^5~
~0 \le h_i, c_i \le N~

Subtask 1 [30%]

~T = 1~

Subtask 2 [70%]

~T = 2~

Input Specification

The first line contains one integer, ~T~, the number of the subtask you must solve.

The second line contains one integer, ~N~.

The third line contains ~N~ space-separated integers, describing ~h_1, h_2, \dots, h_N~ if ~T = 1~, or ~c_1, c_2, \dots, c_N~ if ~T = 2~.

Output Specification

If ~T = 1~, output one line containing ~N~ space-separated integers, ~c_1, c_2, \dots c_N~.

If ~T = 2~, output -1 on one line if a landscape under the given constraints does not exist. Otherwise, output ~N~ space-separated integers in the range ~[0,N]~, ~h_1, h_2, \dots h_N~, describing any landscape which would have produced the given values of ~c_1, c_2, \dots, c_N~ as sea levels rose.

Sample Input 1

1
6
2 1 3 0 4 3

Sample Output 1

2 3 2 1 0 0

Explanation For Sample 1

Since ~T = 1~, we are given ~h_1, h_2, \dots, h_N~ and would like to compute ~c_1, c_2, \dots c_N~. The number of islands at each sea level ~s~ from ~1~ to ~N~ can be counted in each of the following diagrams.

Sample Input 2

2
5
1 3 3 2 1

Sample Output 2

3 1 4 1 5

Explanation for Sample 2

Since ~T = 2~, we are given ~c_1, c_2, \dots, c_N~ and would like to find any landscape ~h_1, h_2, \dots, h_N~ which matches the data. The sample output is one possible landscape which satisfies these constraints. This can be verified in the following diagrams for each sea level ~s~ from ~1~ to ~N~:

Sample Input 3

2
5
1 2 3 4 5

Sample Output 3

-1

Explanation for Sample 3

It can be shown that there does not exist a landscape with ~N~ patches of land and elevations ~h_1, h_2, \dots, h_N~ in the inclusive range ~[0,N]~ which produces the given values of ~c_1, c_2, \dots c_N~.