Problems - Codeforces

Algo Cup 2025 by csspace.io (Finals)

You are standing in front of a huge ladder consisting of $$$n$$$ steps (let's assume you are initially on the step $$$0$$$). You want to climb as high as possible, and to do that, you have $$$x$$$ energy points and a choice of two actions:

Climb up one step higher. To climb to the $$$i$$$-th step from the $$$i-1$$$-th step, you must spend $$$a_i$$$ energy points. If your current energy reserve is less than $$$a_i$$$, you will not be able to climb to the $$$i$$$-th step;
Teleport to one step higher without spending energy but using one teleport charge.

Unfortunately, you do not know how many teleport charges you have left. Therefore, for each number of teleport charges from $$$0$$$ to $$$n-1$$$, determine the maximum step you can reach.

Input

Each test consists of several test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line contains two integers $$$n$$$ and $$$x$$$ ($$$1 \le n \le 3 \cdot 10^5; 1 \le x \le 10^{15}$$$) — the number of steps and the initial amount of energy, respectively.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ is the number of energy points needed to climb to the $$$i$$$-th step (while being on the $$$i-1$$$-th step).

Output

For each test case, print the answer in the following format.

In a single line, print $$$n$$$ numbers $$$s_0, s_1, \dots, s_{n-1}$$$, where $$$s_i$$$ is the maximum step you can reach while spending no more than $$$i$$$ teleport charges.

Example

Input

3
4 5
10 11 15 100
4 1337
1 10 100 1000
5 1
1000 1001 1002 1003 1004

Output

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

You are given a set of strings $$$s_1, s_2, \dots, s_n$$$ consisting of lowercase letters of the Latin alphabet. It is guaranteed that $$$n$$$ is an even number.

A string $$$t$$$ is called perfect if exactly $$$\frac{n}{2}$$$ strings from the set contain $$$t$$$ as a substring.

For example, for the set abc, acb, cab, and cba, the strings ab and cb are perfect, while the strings a, ca, and ooo are not.

Your task is to find the longest perfect substring or report that there is no such substring.

Input

The first line contains a single integer $$$n$$$ ($$$2 \le n \le 1\,000$$$). The number $$$n$$$ is even.

The next $$$n$$$ lines contain the strings, with the $$$i$$$-th line containing the string $$$s_i$$$ ($$$1 \le |s_i| \le 5\,000$$$), consisting of lowercase letters of the Latin alphabet.

Additional input constraint: the sum of the lengths of the strings does not exceed $$$5\,000$$$.

Output

Print the longest perfect substring. If such a substring does not exist, print «No solution» (without quotes). If there are multiple possible answers, print any of them.

Examples

Input

4
abc
acb
cab
cba

Output

ab

Input

2
ccc
dd

Output

ccc

Input

4
acdd
ba
eda
aaad

Output

No solution

Input

2
xx
xx

Output

No solution

Recall that a binary string is a string consisting of the characters 0 and/or 1. A substring of a binary string is defined as its continuous subsequence.

Suppose you have a binary string $$$s$$$. You can perform the following sequence of operations on it:

during the first operation, you can either do nothing or select any substring of length $$$1$$$ consisting of zeros in $$$s$$$ and remove it;
during the second operation, you can either do nothing or select any substring of length $$$2$$$ consisting of zeros in $$$s$$$ and remove it;
during the third operation, you can either do nothing or select any substring of length $$$4$$$ consisting of zeros in $$$s$$$ and remove it;
and so on (during the $$$i$$$-th operation, a substring of length $$$2^{i-1}$$$ is selected).

After each removal, the resulting parts of the string are glued together in the same order. The operations can be terminated at any moment (including leaving the string unchanged).

We call a binary string beautiful if it is possible to remove all zeros from it using such a sequence of operations. For example:

000 is a beautiful string: 000 $$$\rightarrow$$$ 00 $$$\rightarrow$$$ $$$\varepsilon$$$ (where $$$\varepsilon$$$ denotes the empty string);
10100000000100 is a beautiful string: 10100000000100 $$$\rightarrow$$$ 1100000000100 $$$\rightarrow$$$ 11000000001 $$$\rightarrow$$$ 11000000001 $$$\rightarrow$$$ 111;
111 is a beautiful string, as it already contains no zeros;
010100 is not a beautiful string.

Your task is to count the number of beautiful binary strings of length $$$n$$$.

Input

The input consists of a single line containing one integer $$$n$$$ ($$$2 \le n \le 2\,000\,000$$$).

Output

Output a single integer — the number of beautiful binary strings of length $$$n$$$, taken modulo $$$998244353$$$.

Examples

Input

Output

Input

Output

Input

Output

Input

Output

Input

Output

Input

Output

163685965

Note

For $$$n=2$$$, all binary strings are beautiful.

For $$$n=3$$$, all binary strings except 010 are beautiful.

Let the function $$$f$$$ take an array $$$a_1, a_2, \dots, a_n$$$ as input and return an array $$$b_1, b_2, \dots, b_n$$$ according to the following rule: the element $$$b_i$$$ is equal to the number of elements in the prefix of length $$$i$$$ of the array $$$a$$$ that are equal to $$$a_i$$$.

For example:

if $$$a = [7, 7, 7, 1, 7, 4, 1]$$$, then $$$b = [1, 2, 3, 1, 4, 1, 2]$$$;
if $$$a = [1, 2, 1, 2, 1, 2]$$$, then $$$b = [1, 1, 2, 2, 3, 3]$$$;
if $$$a = [1, 2, 3, 3, 2, 1]$$$, then $$$b = [1, 1, 1, 2, 2, 2]$$$.

A sequence of numbers $$$x_1, x_2, \dots, x_n$$$ is called good if there is such an array $$$a$$$ that $$$f(a) = x$$$. For example, the sequence $$$x = [1, 2, 3, 1]$$$ is good, while $$$x = [1, 2, 2]$$$ and $$$x = [1, 2, 4]$$$ are not.

For a given array $$$x_1, x_2, \dots, x_n$$$, determine the number of its subsegments (subarrays of consecutive elements) that are good sequences.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — the length of the array $$$x$$$.

The second line of each test case contains $$$n$$$ integers $$$x_1, x_2, \dots, x_n$$$ ($$$1 \le x_i \le n$$$) — the array $$$x$$$ itself.

Additional constraint on the input data: the sum of $$$n$$$ across all test cases does not exceed $$$10^6$$$.

Output

For each test case, output one integer — the number of subsegments of the array $$$x$$$ that are good sequences.

Example

Input

6
8
1 1 2 2 2 1 2 3
10
1 1 1 1 1 1 1 1 1 1
5
5 4 3 2 1
10
1 2 3 1 2 1 2 1 3 1
6
1 2 3 4 5 1
15
1 1 2 1 2 2 3 2 1 2 3 3 2 1 2

Output

Note

In the first test case, there are $$$9$$$ good subsegments:

$$$x_1 = [1]$$$;
$$$x_1, x_2 = [1, 1]$$$;
$$$x_1, \dots, x_3 = [1, 1, 2]$$$;
$$$x_1, \dots, x_4 = [1, 1, 2, 2]$$$;
$$$x_2 = [1]$$$;
$$$x_2, x_3 = [1, 2]$$$;
$$$x_6 = [1]$$$;
$$$x_6, x_7 = [1, 2]$$$;
$$$x_6, \dots, x_8= [1, 2, 3]$$$.

In the second test case, any subsegment is good.

In the third test case, there is only one good subsegment — $$$x_5 = [1]$$$.

You are given a simple undirected weighted graph consisting of $$$n$$$ vertices and $$$m$$$ edges. The vertices are numbered from $$$1$$$ to $$$n$$$. Vertices $$$x_i$$$ and $$$y_i$$$ are connected by an edge with weight $$$w_i$$$ ($$$1 \le i \le m$$$). An integer $$$a_i$$$ is written on the vertex $$$i$$$ ($$$1 \le i \le n$$$).

The cost of a path $$$v_1, v_2, \dots, v_c$$$ (a path is a sequence of vertices where any two consecutive vertices are connected by an edge) is defined as the sum of weights of all edges on that path.

Let's define beauty of a path $$$v_1, v_2, \dots, v_c$$$ as the sum $$$a_{v_1} + a_{v_2} + \cdots + a_{v_c}$$$. We say that a simple path (a path where each vertex of the graph is included at most once) is beautiful if the beauty of this path is divisible by $$$k$$$ without a remainder.

Your task is to find the beautiful path with the smallest possible cost, or report that such a path does not exist.

Input

The first line contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$2 \le n \le 10^4$$$; $$$1 \le m \le 10^4$$$; $$$2 \le k \le 6$$$) — the number of vertices in the graph, the number of edges in the graph, and the desired divisor of the path beauty value.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \lt a_i \lt k$$$), where $$$a_i$$$ is the number written on the vertex $$$i$$$.

Then $$$m$$$ lines follow, the $$$i$$$-th of them contain three integers $$$x_i$$$, $$$y_i$$$, and $$$w_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$; $$$1 \le w_i \le 10^9$$$), indicating an edge between vertices $$$x_i$$$ and $$$y_i$$$ with weight $$$w_i$$$. The given graph does not contain self-loops or multiple edges.

Output

Print a single integer — the minimum possible cost of a beautiful path or -1 if there is no such path.

Examples

Input

Output

Input

2 1 4
2 3
1 2 1

Output

-1

You are given two sequences of integers $$$a_1, a_2, \ldots, a_n$$$ and $$$b_1, b_2, \ldots, b_n$$$.

Determine the minimum number of exchanges of pairs of elements in the sequence $$$a$$$ required for $$$a$$$ to match $$$b$$$.

Input

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 30$$$) — the length of the sequences.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$).

The third line contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le n$$$).

It is guaranteed that $$$a$$$ and $$$b$$$ are equal when the elements within each of them are sorted in non-decreasing order. Elements in the sequences may repeat.

Output

In the first line, print $$$m$$$ — the minimum number of exchanges required to transform $$$a$$$ into $$$b$$$.

In the $$$i$$$-th of the following $$$m$$$ lines, print two distinct integers $$$x_i, y_i$$$ ($$$1 \le x_i, y_i \le n$$$), indicating that in the $$$i$$$-th exchange, $$$a_{x_i}$$$ and $$$a_{y_i}$$$ should be swapped.

Examples

Input

3
1 2 3
3 2 1

Output

1
1 3

Input

4
1 1 2 2
2 2 1 1

Output

2
2 3
1 4

Input

9
1 3 2 2 1 3 3 2 1
2 1 3 3 2 1 1 3 2

Output

You are given a matrix of size $$$n \times m$$$, consisting of positive integers.

You can choose any starting cell of the matrix. In one move, you can either move down or to the right in the matrix. A move from cell $$$(n, j)$$$ down moves you to cell $$$(1, j)$$$, and a move from cell $$$(i, m)$$$ to the right moves you to cell $$$(i, 1)$$$. Your task is to make exactly $$$n$$$ moves down and exactly $$$m$$$ moves to the right, returning to the original cell in such a way that no cell in the matrix is visited twice (except for the starting cell).

Find a way to choose the starting cell and make $$$n+m$$$ moves as described above, such that the sum of the numbers in the visited cells is maximal.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n, m \le 1\,500$$$) — the dimensions of the matrix.

The next $$$n$$$ lines contain $$$m$$$ positive integers each, where the $$$i$$$-th of these lines contains the numbers $$$a_{i, 1}, a_{i, 2}, \ldots, a_{i, m}$$$ ($$$1 \le a_{i, j} \le 1\,000\,000$$$).

Output

In the first line, print the maximum sum that can be obtained with $$$n+m$$$ moves.

In the second line, print two numbers $$$r$$$ and $$$c$$$ — the row and column number of the starting cell in the optimal way.

In the last line, print a string of $$$n+m$$$ characters consisting of exactly $$$n$$$ characters 'D' and exactly $$$m$$$ characters 'R', corresponding to the optimal sequence of moves. The character 'D' corresponds to a move down, and the character 'R' corresponds to a move to the right.

Examples

Input

2 2
1 2
3 4

Output

10
1 1
DRDR

Input

Output

37
1 2
DRDRRD

Input

Output

46
1 1
DRRDRD

Input

3 7
74 68 24 42 27 1 81
57 67 49 40 1 92 83
34 88 86 45 32 48 24

Output

613
1 2
DDRRRRRDRR

You are given a weighted planar graph ($$$^{\text{∗}}$$$) with $$$n$$$ vertices and $$$m$$$ edges.

You are required to find two sets in it: a set $$$T$$$ of triangles ($$$^{\text{†}}$$$) and a set $$$S$$$ of edges such that:

Any two triangles in $$$T$$$ do not share an edge;
If all edges in $$$S$$$ are removed from the graph, there will be no triangles left;
$$$|S| \le 2|T|$$$;
The sum of the weights of the edges in $$$S$$$ does not exceed twice the sum of the weights of the triangles in $$$T$$$, where the weight of a triangle is the weight of its heaviest edge.

$$$^{\text{∗}}$$$Planar graph — a graph that can be drawn on a plane without edge intersections except at vertices.

$$$^{\text{†}}$$$A triangle is a triplet of vertices, each pair of which is connected by an edge

Input

Each test consists of several test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1023$$$) — the number of test cases. The following lines describe the test cases.

The first line of a test case contains two integers $$$n$$$, $$$m$$$ ($$$2 \le n \le 300\,000$$$, $$$0 \le m \le 3n-6$$$) — the number of vertices and edges in the graph, respectively. The vertices are numbered with integers from $$$1$$$ to $$$n$$$, and the edges are numbered with integers from $$$1$$$ to $$$m$$$.

The next $$$m$$$ lines contain the description of the edges; the $$$i$$$-th line contains three integers $$$a_i$$$, $$$b_i$$$, $$$w_i$$$ ($$$1 \le a_i \lt b_i \le n$$$, $$$1 \le w_i \le 10^9$$$), meaning that the $$$i$$$-th edge connects vertex $$$a_i$$$ with vertex $$$b_i$$$ and has weight $$$w_i$$$.

It is guaranteed that the graph is planar and does not contain loops or multiple edges.

The sum of $$$n$$$ across all test cases does not exceed $$$300\,000$$$.

Output

For each test case, output two non-negative integers $$$s$$$ and $$$t$$$ — the sizes of $$$S$$$ and $$$T$$$, respectively.

In the next $$$s$$$ lines, output the numbers $$$x_{i, 1}, x_{i, 2}$$$ ($$$1 \le x_{i,1}, x_{i,2} \le n$$$) — the endpoints of the $$$i$$$-th edge in the set $$$S$$$.

In the following $$$t$$$ lines, output the numbers $$$y_{j, 1}, y_{j, 2}, y_{j, 3}$$$ ($$$1 \le y_{j, 1}, y_{j, 2}, y_{j, 3} \le n$$$) — the vertices that make up the $$$j$$$-th triangle in the set $$$T$$$.

The edges in $$$S$$$ and the triangles in $$$T$$$, as well as the endpoints of the edges and the vertices of the triangles, can be output in any order.

Example

Input

Output