Baozii Cup 1
A. Chtholly Tree
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The Chtholly Tree is a data structure used for certain sequence maintenance problems. Each node in a Chtholly Tree represents a consecutive block of equal elements in the sequence. These nodes are maintained in any type of sorted data structure such as set in C++ or a balanced binary search tree.

For example, the Chtholly Tree of the sequence $$$[1,2,3,3,2,2,1,1]$$$ will contain the following nodes: $$$[1,1]$$$, $$$[2,2]$$$, $$$[3,4]$$$, $$$[5,6]$$$, $$$[7,8]$$$.

Problems solvable using Chtholly Tree usually involve the following type of operation: choose a segment $$$[l,r]$$$ of the sequence, and for all $$$l \le i \le r$$$, set $$$a_i=x$$$ for some value $$$x$$$. It can be proven that if $$$l$$$, $$$r$$$, and $$$x$$$ are chosen randomly, the expected number of nodes in a Chtholly Tree is $$$O(\log n)$$$, where $$$n$$$ is the length of the sequence.

However, Baozii would like to know the exact expected number of nodes rather than its asymptotic representation. To do so, he did the following experiment:

  1. He begins with a sequence of length $$$n$$$, initially filled with $$$0$$$.
  2. In the $$$i$$$-th operation ($$$1 \le i$$$), he chooses a segment $$$[l,r]$$$ randomly and sets all values in it to $$$i$$$.

After a sufficiently large number of operations, Baozii observed that the number of nodes seems to converge to around $$$2 \ln n$$$. Now for a given $$$n$$$, can you help Baozii find the exact expected number of nodes?

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows.

The only line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 10^{18}$$$) — the length of the initial sequence.

Output

For each test case, output a real number: the expected number of nodes in the Chtholly Tree. The absolute difference between your answer and the jury's answer should not be more than $$$10^{-3}$$$.

Example
Input
5
1
2
3
4
5
Output
1.000000
1.666667
2.200000
2.642857
3.020202

B. GoGo
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Baozii prefers using Go for programming problems that demand efficiency. In this task, Baozii challenges you to implement an interpreter for a simplified version of Go, called GoGo.

  1. Program Structure:
    • Every GoGo program starts with a main function, declared as func main() { on the first line.
    • The main function ends with a closing brace on its final line.

  2. Data Types and Variable Declarations:
    • GoGo supports two types: int (integer) and string.
    • Variables are declared using the syntax var x type, where x is the variable name and type is its data type (int or string).
    • Declared variables are initialized with their type's default value: $$$0$$$ for integers and an empty string for strings.
    • Re-declaration of a variable will lead to a runtime error.

  3. Literals:
    • Integer literals: Written in decimal, within the 64-bit signed integer range, and without leading zeroes.
    • String literals: Enclosed in double quotes and contain only lowercase English letters and digits.

  4. Variable Assignment:
    • Use x = y to assign the value of y to x.
    • x must be a declared variable, and y must be either a declared variable or a literal of the same type.
    • Assignments are pass-by-value, meaning changes to x or y afterward do not affect each other.
    • Violating any of these rules raises a runtime error.
    • Note that it is possible for x to be the same variable as y.

  5. Addition Operation:
    • Use x += y to add y to x.
      • If x and y are integers, this increments x by y.
      • If x and y are strings, this concatenates y to the end of x.
    • x must be a declared variable, and y must be either a declared variable or a literal of the same type. x and y must be of the same type. Violation of any of these rules will result in a runtime error.
    • Note that it is possible for x to be the same variable as y.

  6. Loops:
    • GoGo has a single loop type: for range n {, where n is the number of iterations (a positive integer literal no more than $$$100$$$).
    • The loop body ends with a closing brace on a single line.
    • No variable declarations or nested loops are allowed within for loops.

  7. Output:
    • Use Println(x) to print x to standard output.
    • If x is an integer, its decimal representation is printed. If x is a string, the string itself is printed.
    • x can be either a literal or a variable. If x is an undeclared variable, a runtime error occurs.
    • Each Println call moves the cursor to the next line.

You are now given a GoGo script. Your interpreter should output exactly what the program will output if it is run, and report any runtime errors.

Some possible clarifications:

  • For simplicity, there will be no indentation or empty lines in the script.
  • All variable names consist only of lowercase English letters and are no more than $$$3$$$ characters long. It is guaranteed that variable names do not coincide with keywords in GoGo such as var or for.
  • Except for possible type mismatch and use of undeclared variables, the script adheres to the given rules and there are no other sources of errors.
  • All operations will keep integers within 64-bit signed integer range. The sum of lengths of all string variables will be no more than $$$10^4$$$ at any time when executing the script.
Input

A GoGo script consisting of no more than $$$10^4$$$ characters.

Output

If a runtime error occurs, output "runtime error"(without quotes) on a single line only. Otherwise, output exactly what is printed to the standard output if the GoGo script is run. It is guaranteed that the total number of characters printed will be no more than $$$10^4$$$.

Examples
Input
func main() {
var x int
var y int
y = -10
Println(y)
var s string
s = "abc"
for range 5 {
Println(1)
Println(x)
x += x
x += 1
s += "p"
s += ""
}
Println("")
Println(s)
Println(x)
}
Output
-10
1
0
1
1
1
3
1
7
1
15

abcppppp
31
Input
func main() {
Println(x)
}
Output
runtime error
Input
func main() {
var x int
var x int
}
Output
runtime error

C. Dominoes Covering
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Baozii presents to you a strip of $$$n$$$ cells, all initially white. You are given a target pattern consisting of $$$n$$$ cells, where each cell is either white or black. Your task is to determine whether it is possible to transform the strip into the given target pattern by performing a finite sequence of the following operation:

  • Choose an integer $$$i$$$ ($$$1 \le i \lt n$$$). Then color the $$$i$$$-th cell white and the $$$(i+1)$$$-th cell black, overriding their initial colors.

Determine if the transformation is achievable. If so, output a valid sequence of operations.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$2 \le n \le 100$$$) — length of Baozii's strip.

The second line contains a binary string of length $$$n$$$, representing the pattern. If the $$$i$$$-th character is 1, the $$$i$$$-th cell should be colored black; otherwise, the $$$i$$$-th cell should be colored white.

Output

For each test case, output "YES" (without quotes) if there exists a finite sequence of operations which colors the strip to the given pattern, and "NO" (without quotes) otherwise.

If the answer is "YES", output the sequence in the following format:

  • On the first line, output a single integer $$$k$$$ ($$$0 \le k \le 1000$$$) — the number of operations. We can prove that if there exists a valid sequence, there exists one with no more than $$$1000$$$ operations.
  • The second line contains $$$k$$$ integers $$$a_1,a_2,\ldots,a_k$$$ ($$$1 \le a_i \lt n$$$), where $$$a_i$$$ represents the index chosen for the $$$i$$$-th operation.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Example
Input
4
5
01010
2
10
10
0111100100
3
000
Output
YES
2
1 3
NO
YES
9
7 7 7 7 4 3 2 1 1
YES
0

D. Coprime
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an integer $$$n$$$. Construct a $$$n \times n$$$ matrix $$$M$$$ that contains each integer from $$$1$$$ to $$$n^2$$$ exactly once. The $$$\gcd$$$ of all numbers in each row should be equal to $$$1$$$, and the $$$\gcd$$$ of all numbers in each column should be equal to $$$1$$$.

Formally, $$$M$$$ has to satisfy the following conditions:

  • $$$\gcd(M_{i,1},M_{i,2},\ldots,M_{i,n})=1$$$ for all $$$1 \le i \le n$$$.
  • $$$\gcd(M_{1,j},M_{2,j},\ldots,M_{n,j})=1$$$ for all $$$1 \le j \le n$$$.
Input

Each test contains multiple test cases. The first line of each test contains an integer $$$t$$$ ($$$1 \le t \le 200$$$) — the number of test cases.

The only line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 500$$$) — the size of $$$M$$$ to be constructed.

It is guaranteed that the sum of $$$n^2$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, if no possible $$$M$$$ exists, output $$$-1$$$.

Otherwise, output $$$n$$$ lines of $$$n$$$ integers each, where the $$$j$$$-th integer on the $$$i$$$-th line represents $$$M_{i,j}$$$.

Example
Input
3
1
2
3
Output
1
1 2
4 3
1 2 3
4 5 6
9 8 7

E. OIer's Dream(Chaser)
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of $$$n$$$ integers. Find:

$$$$$$\max_{1 \le i,j \le n} \gcd(a_i,a_j) + (a_i \oplus a_j)$$$$$$

where $$$\oplus$$$ denotes the bitwise XOR operation.

Input

The first line of each test contains an integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10 ^5$$$) — the length of $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 5 \cdot 10^5$$$) — the elements of $$$a$$$.

Output

Output an integer representing the maximum value of the expression above.

Examples
Input
3
1 2 3
Output
4
Input
5
9 9 3 8 2
Output
13

F. Big Baozi, Small Baozi
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

DreamChaser is excited about a new video game, Big Baozi, Small Baozi. In this game, he plays as a Baozi trying to consume other Baozi to grow bigger.

The game's map is represented by an undirected connected graph with $$$n$$$ vertices and $$$m$$$ edges. Each vertex contains a Baozi with a weight $$$w_u$$$ ($$$1 \leq u \leq n$$$).

The game consists of $$$q$$$ rounds. At the start of each round:

  • The graph resets to its original state.
  • DreamChaser becomes the Baozi at vertex $$$v$$$ with an additional weight boost of $$$x$$$. Thus, his initial weight for that round is $$$w_v + x$$$. The values of $$$v$$$ and $$$x$$$ may vary across rounds.

After the round begins, DreamChaser can perform the following operation repeatedly:

  • If there is a neighboring Baozi with a weight no greater than his current weight, he consumes it.
  • When a Baozi is consumed, its weight is added to DreamChaser's weight.
  • The neighbors of the consumed Baozi become DreamChaser's neighbors.

This process continues until there are no consumable neighbors left. For each round of the game, please help DreamChaser determine his final weight at the end of the round.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). The description of the test cases follows.

The first line of each test case contains three integers $$$n$$$, $$$m$$$ and $$$q$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$n - 1 \le m \le \min(2 \cdot 10^5, \frac{n(n-1)}{2})$$$, $$$1 \le q \le 2 \cdot 10^5$$$) — the number of vertices, edges, and rounds respectively.

The second line contains $$$n$$$ integers $$$w_1,,w_2,\ldots,w_n$$$ ($$$1 \le w_i \le 10^9$$$) — the weight of the Baozi on each vertex.

Each of the next $$$m$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le n$$$, $$$u \ne v$$$), representing an edge between vertices $$$u$$$ and $$$v$$$. It is guaranteed that there are no self loops or multiple edges in the graph.

Each of the next $$$q$$$ lines contains two integers $$$v$$$ and $$$x$$$ ($$$1 \le v \le n$$$, $$$0 \le x \le 10^9$$$) — the starting vertex and additional weight boost for each round.

It is guaranteed that the sum of $$$n$$$, $$$m$$$ and $$$q$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output $$$q$$$ integers, where the $$$i$$$-th integer represents the final weight of DreamChaser for the $$$i$$$-th round.

Example
Input
1
5 4 4
1 2 2 5 11
1 2
2 3
5 4
3 4
1 0
4 0
4 1
2 10
Output
1
10
22
31

G. Find the Second Maximum
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

There is a hidden array $$$a$$$ of length $$$n$$$, consisting of distinct positive integers no larger than $$$10^9$$$. Your task is to find the second maximum element of $$$a$$$. To achieve this, you may query a non-empty range $$$[l,r]$$$ $$$(1 \le l \le r \le n)$$$, and the judge will return you the maximum element among $$$a_l, a_{l+1}, \ldots, a_r$$$.

You may not use more than $$$24$$$ queries.

Input

Each test contains multiple test cases. The first line contains one integer $$$t$$$ ($$$1\le t\le500$$$) — the number of test cases. The description of each test case follows.

The first line of each test case contains one integer $$$n$$$ ($$$2\le n\le1000$$$) — the length of the hidden array $$$a$$$.

Interaction

To ask a query, output a line in the following format:

  • ? l r

where $$$[l,r]$$$ is the query range.

After each query, you should read one line containing one integer, denoting the maximum element among $$$a_l,a_{l+1},\ldots,a_r$$$.

Print the answer in a line in the following format:

  • ! x i

where $$$x$$$ is the value of the second maximum element, and $$$i$$$ ($$$1 \le i \le n$$$) is the index of $$$x$$$ in $$$a$$$.

Note that printing the answer is not counted towards the total number of queries.

You can ask at most $$$24$$$ queries in each test case.

The interactor is NOT adaptive, meaning that the answer is known before the participant asks the queries and doesn't depend on the queries asked by the participant.

If your program makes more than $$$24$$$ queries for one test case, your program should immediately terminate to receive the verdict Wrong Answer. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.

After printing a query do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

  • fflush(stdout) or cout.flush() in C++;
  • System.out.flush() in Java;
  • flush(output) in Pascal;
  • stdout.flush() in Python;
  • see the documentation for other languages.
Example
Input
1
10

9

10

6

1
Output


? 1 3

? 2 10

? 9 10

? 3 3

! 9 1
Note

In the sample test case, the hidden array $$$a$$$ is $$$[9,8,1,3,2,10,5,7,6,4]$$$.

  • In the first query, the maximum element among $$$a_1,a_2,a_3$$$ is $$$9$$$.
  • In the second query, the maximum element among $$$a_2,a_3,\ldots,a_{10}$$$ is $$$10$$$.
  • In the third query, the maximum element among $$$a_9,a_{10}$$$ is $$$6$$$.
  • In the fourth query, the maximum element among $$$a_3$$$ is $$$1$$$.

H. The Easiest Problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of length $$$n$$$ containing positive integers. You are allowed to rearrange the elements of $$$a$$$ in any order. Find the minimum possible value of the following expression: $$$$$$\sum_{i=1}^{n-1} \frac{a_{i}^2 + a_{i+1}^2}{a_i a_{i+1}}$$$$$$

Input

Each test case contains multiple test cases. The first line of each test contains an integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the length of $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^6$$$) — the elements of $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case, output a real number: the minimum possible value of the given expression.

Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.

Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$.

Example
Input
2
2
1 2
3
11451 19198 114514
Output
2.5000000000
8.4055429827

I. Expected Value
time limit per test
12 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

For a set $$$S$$$ and an array $$$a$$$ of length $$$n$$$, where $$$n$$$ is even, define $$$f(a, S)$$$ to be the number of permutations $$$p$$$ of $$$\{1,2,\ldots,n \}$$$ such that $$$a_{p_i}+a_{p_{n-i+1}} \in S$$$ for all $$$1 \le i \le n$$$.

You are given a set $$$T$$$ and $$$m$$$ sets $$$A_1,A_2,\ldots,A_m$$$, where $$$m$$$ is even. Now construct another array $$$b$$$ as follows:

  1. Initialise $$$b$$$ as an empty array.
  2. For each index from $$$1$$$ to $$$m$$$:
    • Choose an integer from $$$A_i$$$ randomly, with the probability of selecting each integer proportional to its frequency of occurrence in $$$A_i$$$.
    • Append the selected integer to the end of $$$b$$$.

Find the expected value of $$$f(b,T)$$$, modulo $$$998244353$$$.

Input

The first line of each test contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^4$$$, $$$2 \le m \le 30$$$, $$$m$$$ is even) — the size of $$$T$$$ and the number of arrays.

The second line contains $$$n$$$ distinct integers $$$T_1,T_2,\ldots,T_n$$$ ($$$0 \le T_i \le 2 \cdot 10^4$$$) — the elements of $$$T$$$.

The $$$2i-1$$$-th line of the next $$$2m$$$ lines contains an integer $$$k_i$$$ ($$$1 \le k_i \le 10^4$$$) — the size of $$$A_i$$$.

The $$$2i$$$-th line contains $$$k_i$$$ integers $$$A_{i,1},A_{i,2},\ldots,A_{i,k_i}$$$ ($$$0 \le A_{i,j} \le 10^4$$$) — the elements of $$$A_i$$$.

Output

Output an integer indicating the expected value of $$$f(b,T)$$$ modulo $$$998244353$$$. Formally, let $$$M=998244353$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \ne 0$$$. Output $$$p \cdot q ^{-1} \bmod M$$$, where $$$q^{-1}$$$ denotes the multiplicative inverse of $$$q$$$ modulo $$$M$$$.

Examples
Input
1 2
0
2
0 1
2
0 1
Output
499122177
Input
3 4
2 3 4
3
0 2 2
5
1 2 1 1 1
1
1
2
0 3
Output
798595492

J. Pseudo Merge Sort
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

For any two integer arrays $$$a$$$ and $$$b$$$ of lengths $$$n$$$ and $$$m$$$, each containing distinct elements and there are no common elements between them, define $$$f(a,b)$$$ as follows:

$$$$$$ f(a,b) = \begin{cases} \emptyset & a = \emptyset \land b = \emptyset \\ a & b = \emptyset \\ b & a = \emptyset \\ [a_1]+f([a_2,a_3,\ldots,a_n],b) & a_1 \lt b_1 \\ [b_1]+f(a,[b_2,b_3,\ldots,b_m]) & a_1 \gt b_1 \end{cases} $$$$$$

where $$$+$$$ is defined as the concatenation of two arrays.

You are now given a permutation $$$p$$$ of length $$$2n$$$. You need to determine whether it is possible to find two arrays $$$a$$$ and $$$b$$$, both of length $$$n$$$ and together containing all integers from $$$1$$$ to $$$2n$$$ exactly once, such that $$$f(a,b)=p$$$.

A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — half the length of $$$p$$$.

The second line contains $$$2n$$$ integers $$$p_1,p_2,\ldots,p_{2n}$$$ ($$$1 \le p_i \le 2n$$$) — the permutation $$$p$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, if there exist $$$a$$$, $$$b$$$ satisfying the constraints, output YES; otherwise, output NO. You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Example
Input
3
2
2 3 1 4
2
3 1 2 4
4
3 2 6 1 5 7 8 4
Output
YES
NO
YES

K. The Tree Problem
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Let $$$a$$$ be a sequence of integers and $$$k$$$ be a given integer. Define $$$f(a)$$$ to be the largest element that appears at least $$$k$$$ times in the sequence. Specially, if all elements of $$$a$$$ occur less than $$$k$$$ times, then $$$f(a)=0$$$.

You are given an undirected tree with $$$n$$$ vertices rooted at vertex $$$1$$$. Recall that a tree is a connected acyclic graph. Each vertex $$$i$$$ has a value $$$v_i$$$ assigned to it. We say that $$$j$$$ is in the subtree of $$$i$$$ if and only if:

  • $$$i=j$$$ or
  • $$$i$$$ is on the simple path from $$$j$$$ to the root.

The problem is as follows: for each vertex $$$i$$$, calculate $$$f(a_i)$$$, where $$$a_i$$$ is the sequence of $$$v_j$$$ for all $$$j$$$ in the subtree of $$$i$$$.

Input

Each test contains multiple test cases.

The first line of each test contains one integer $$$t$$$ ($$$1\le{t}\le1000$$$) – the number of test cases.

The first line of each test case contains two integers $$$n,k$$$ ($$$1\le{n}\le2\cdot{10^5}$$$, $$$1 \le k \le 2 \cdot 10^5$$$) – the number of vertices in the given tree.

The second line contains $$$n$$$ integers $$$v_1,v_2,\ldots{v_n}$$$ ($$$1\le{v_i}\le{10^9}$$$) – the value of each vertex.

Then follows $$$n-1$$$ lines:

Each line contains two integers $$$i,j$$$ ($$$1\le{i,j}\le{n}$$$) – indicating an edge between the vertices $$$i$$$ and $$$j$$$.

It is guaranteed that the given input forms a valid tree rooted at $$$1$$$.

It is further guaranteed that the sum of all $$$n$$$ across the test cases does not exceed $$$2\cdot{10^5}$$$.

Output

For each test case, output $$$n$$$ integers in a single line: the $$$i$$$-th integer represents the value $$$f(a_i)$$$.

Example
Input
3
5 2
3 3 3 3 3
1 2
3 5
2 3
5 4
5 2
4 4 3 3 5
1 2
2 3
3 4
4 5
3 3
114514 114514 114514
1 3
3 2
Output
3 3 3 0 3 
4 3 3 0 0 
114514 0 0

L. ChaseDreamer
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

DreamChaser is an employee at Baozii Corporations. As a considerate boss, Baozii provides a daily transportation allowance of $$$k$$$ dollars for each employee before they go home after work. To complete an ongoing project, DreamChaser must work overtime for $$$n$$$ consecutive days. Fortunately, the company offers $$$m$$$ shuttle services each day to send employees home.

The cost and arrival time of each shuttle are represented by two matrices, $$$c$$$ and $$$t$$$. Specifically, $$$c_{i,j}$$$ represents the cost of the $$$j$$$-th shuttle on the $$$i$$$-th day, and $$$t_{i,j}$$$ represents the time at which the $$$j$$$-th shuttle on the $$$i$$$-th day arrives at DreamChaser's home.

DreamChaser plans to use only the transportation allowance provided by the company to take the shuttles. Note that any unused transportation allowance from previous days can be carried over to subsequent days, but at no point can DreamChaser's funds become negative. Additionally, DreamChaser must return home every day.

For a time $$$s$$$, if DreamChaser can return home no later than $$$s$$$, then $$$s$$$ is considered good. Find the smallest good $$$s$$$, or report it does not exist.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows.

The first line of each test case contains three integers $$$n$$$, $$$m$$$, $$$k$$$ ($$$1 \le n \le 1000$$$, $$$1 \le m \le 1000$$$, $$$1 \le k \le 10^9$$$) — the number of days of working overtime, and the number of shuttle services provided.

The following $$$n$$$ lines describe the matrix $$$c$$$, where the $$$i$$$-th line contains $$$m$$$ integers $$$c_{i,1},c_{i,2},\ldots,c_{i,m}$$$ ($$$1 \le c_{i,j} \le 10^9$$$).

The following $$$n$$$ lines describe the matrix $$$t$$$, where the $$$i$$$-th line contains $$$m$$$ integers $$$t_{i,1},t_{i,2},\ldots,t_{i,m}$$$ ($$$1 \le t_{i,j} \le 10^9$$$).

It is guaranteed that the sum of $$$n$$$ and $$$m$$$ over all test cases does not exceed $$$1000$$$.

Output

For each test case, if the transportation allowance is enough, output the smallest good $$$s$$$. Otherwise, output $$$-1$$$.

Example
Input
1
3 2 3
3 4
2 3
3 4
1 1
3 2
3 4
Output
3

M. The Other Tree Problem
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an undirected tree with $$$n$$$ vertices rooted at $$$1$$$. Recall that a tree is a connected acyclic graph. You are also given a permutation $$$p$$$ of length $$$n$$$. A preorder traversal of a rooted tree with $$$n$$$ vertices is a permutation of length $$$n$$$ that can be generated by the following pseudo-code:

seq = list()

function preorder(u):

    seq.append(u)

    shuffle(children(u))

    for v in children(u):

        preorder(v)

preorder(1)

where seq is the generated preorder traversal. Note that there might be more than $$$1$$$ possible preorder traversals of a tree.

Among all possible preorder traversals, you need to find one such that the following sum is maximised: $$$$$$\sum_{i=1}^n \left[p_i=s_i \right]$$$$$$

where $$$s$$$ is the preorder traversal you have chosen. Informally, you need to find a preorder traversal $$$s$$$ such that it has the most number of matching positions with $$$p$$$.

If there are many possible solutions, you may output any of them.

Input

The first line of each test contains a single integer $$$n$$$ ($$$1 \le n \le 18$$$) — the number of vertices in the given tree.

The second line contains $$$n$$$ distinct integers $$$p_1,p_2,\ldots,p_n$$$ ($$$1 \le p_i \le n$$$) — the given permutation.

Each of the next $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le n$$$, $$$u \ne v$$$), indicating an edge between vertices $$$u$$$ and $$$v$$$.

It is guaranteed that the input forms a tree.

Output

Output $$$n$$$ integers, representing the preorder traversal you found.

Example
Input
5
3 5 2 4 1
1 2
5 4
3 2
1 4
Output
1 2 3 4 5