The 2023 Damascus University Collegiate Programming Contest
A. Salahiano-utiful Arrays
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Salahiano came up with this problem with a totally different story that none of the judges was able to understand. He changed the story multiple times until finally, it became humanly understandable.

We define an array of integers to be a Salahiano-utiful Array if it's elements are distinct.

Salahiano will give you two arrays $$$A$$$ and $$$B$$$ of the same length $$$N$$$. In one operation, you can choose some index $$$i$$$ $$$(1 \le i \le N)$$$ and:

  • Exchange the values of $$$A_i$$$ and $$$B_i$$$, i.e swap$$$(A_i, B_i)$$$.

What is the minimum number of operations needed to make both $$$A$$$ and $$$B$$$ Salahiano-utiful Arrays? Or report that it's impossible.

Input

The first line of input contains a single integer $$$T$$$ $$$(1 \le T \le 10^5)$$$ — the number of testcases.

The first line of each testcase contains a single integer $$$N$$$ $$$(1 \le N \le 10^5)$$$ — the length of the arrays $$$A$$$ and $$$B$$$.

Then, $$$N$$$ lines follow, the $$$i_{th}$$$ of them contains the values $$$A_i$$$ and $$$B_i$$$ $$$(1 \le A_i,B_i \le 2 \cdot N)$$$

It's guaranteed that the sum of $$$N$$$ over all testcases does not exceed $$$10^5$$$

Output

For each testcase output a single integer — the minimum possible number of operations needed or $$$-1$$$ if it is impossible.

Example
Input
3
3
1 3
3 2
1 2
2
1 2
1 1
5
1 9
10 3
10 3
2 5
7 5
Output
1
-1
2

B. Osama-utiful Components
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Osama started his life with his teammate Tareq, so he learnt multiple bad habits from him. One of the bad habits Osama learnt is called: "The Blender of Standards". It's a technique where you merge multiple standard problems into one complicated problem. Unfortunately for you, Osama is one of the setters for this contest.

Osama will give you a graph of $$$N$$$ vertices. The graph initially has no edges. Each vertex $$$i$$$ of the graph has a value $$$A_i$$$. Osama wants you to process $$$Q$$$ queries. Each query is one of the following forms:

  • 1 u v: which means you should add an edge between vertices $$$u$$$ and $$$v$$$.
  • 2 u t: which means you should calculate the Osama-uty of the connected component $$$S$$$ that contains vertex $$$u$$$ after the first $$$t$$$ queries $$$(1 \le t \le Q)$$$ (among queries of both types).

To calculate the Osama-uty of some connected component $$$S$$$:

  • Imagine an array $$$B$$$ of length $$$N$$$, such that $$$B_i = 1$$$ if there is at least one vertex $$$u$$$ in $$$S$$$ such that $$$A_u = i$$$. Otherwise, $$$B_i=0$$$.
  • The Osama-uty of the connected component $$$S$$$ is equal to the number of subsegments $$$(L,R)$$$ $$$(1 \le L \le R \le N)$$$ such that:
    • Values $$$B_L, B_{L+1},\dots,B_{R-1}, B_R$$$ are all equal to $$$1$$$.
    • $$$L=1$$$, or $$$B_{L-1}=0$$$.
    • $$$R=N$$$, or $$$B_{R+1}=0$$$.

Osama gave this problem a second thought and found out that it was still pretty easy, so he decided to modify the way of giving the input. Please read the input section and the notes section carefully.

Note that the graph may contain self loops and multiple edges.

Input

The first line of the input contains two integers $$$N$$$ and $$$Q$$$ $$$(1 \le N \le 10^5$$$, $$$1 \le Q \le 2\cdot10^5)$$$.

The second line of the input contains $$$N$$$ space-separated integers $$$A_1, A_2, \dots, A_N$$$ $$$(1 \le A_i \le N)$$$, the values written on the vertices.

Each line of the next $$$Q$$$ lines contains four integers describing the queries.

If the current query is an add query, the input will be:

  • $$$1$$$ $$$u'$$$ $$$v'$$$ $$$x$$$. $$$(1 \le u', v' \le N, 0 \le x \lt i)$$$.

If the current query is an ask query, the input will be:

  • $$$2$$$ $$$u'$$$ $$$t'$$$ $$$x$$$. $$$(1 \le u', t' \le N, 0 \le x \lt i)$$$.
It's guaranteed that $$$x=0$$$ in the first query.

Read the notes section for more information.

Output

For each query of the second type, print a single line containing the Osama-uty of the connected component $$$S$$$ of the vertex $$$u$$$ after the first $$$t$$$ queries.

Examples
Input
3 4
1 2 3
1 3 1 0
2 3 1 1
1 3 2 1
2 3 3 1
Output
1
1
Input
3 5
1 1 3
1 3 1 0
2 3 1 1
1 3 2 1
2 3 3 1
2 3 3 4
Output
1
2
1
Note

Input description: we will assume that the current query is the $$$i_{th}$$$ query.

  • If the current query is an add query, we set $$$u_i = (u' \cdot ans_x \bmod n) + 1$$$ and $$$v_i = (v' \cdot ans_x \bmod n) + 1$$$.
  • If the current query is an ask query, we set $$$u_i = (u' \cdot ans_x \bmod n) + 1$$$ and $$$t_i = (t' \cdot ans_x \bmod i) + 1$$$.
  • $$$ans_x$$$ is the answer to the $$$x_{th}$$$ query.
  • If $$$x$$$ is equal to zero or the $$$x_{th}$$$ query is an add query then $$$ans_x = 1$$$.

In the first example:

  • In the first query, $$$u = 1$$$ and $$$v = 2$$$ $$$(x = 0$$$ means that $$$ans_x = 1)$$$.
  • In the second query, $$$u = 1$$$ and $$$t = 2$$$ (query $$$1$$$ is an add query so $$$ans_1 = 1$$$). During the second query, the connected component of $$$u$$$ contains vertices $$$\{1,2\}$$$, so there is one subsegment $$$[1, 2]$$$ that satisfies the conditions so the Osama-uty is 1.
  • In the third query, $$$u = 1$$$ and $$$v = 3$$$.
  • In the last query, $$$u = 1$$$ and $$$t = 4$$$. There is one subsegment $$$[1, 3]$$$ that satisfies the conditions so the Osama-uty is 1.

In the second example:

  • In the first query, $$$u = 1$$$ and $$$v = 2$$$.
  • In the second query, $$$u = 1$$$ and $$$t = 2$$$. There is one subsegment $$$[1, 1]$$$ that satisfies the conditions so the Osama-uty is 1.
  • In the third query, $$$u = 1$$$ and $$$v = 3$$$.
  • In the 4th query, $$$u = 1$$$ and $$$t = 4$$$. There are two subsegment $$$[1, 1]$$$ $$$[3,3]$$$ that satisfy the conditions so the Osama-uty is 2.
  • In the last query, $$$u = (3 \cdot 2 \bmod 3) + 1 = 1$$$, $$$t = (3 \cdot 2 \bmod 5) + 1 = 2$$$. During the second query, the connected component of $$$u$$$ contains vertices $$$\{1, 2\}$$$ having values $$$\{1, 1\}$$$, so there is one subsegment $$$[1, 1]$$$ that satisfies the conditions so the Osama-uty is 1.

C. Ammar-utiful Permutations
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Turns out Ammar is not that bad at setting problems, as he came up with this problem himself. He wasn't as good as the other judges at coming up with new and fun problem ideas. So instead, he came up with the answer to the problem first, and that's how he proposed this problem.

We define a permutation $$$P$$$ of length $$$N$$$ to be called an Ammar-utiful permutation if it satisfies the following condition:

  • There's exactly one index $$$i$$$, $$$(1 \le i \lt N)$$$ where $$$P_i + P_{i + 1}$$$ is odd.

Given an integer $$$N$$$, you must find an Ammar-utiful permutation $$$P$$$ of length $$$N$$$.

A permutation of length $$$N$$$ is an array of size $$$N$$$ consisting of $$$N$$$ distinct integers in the range $$$[1, N]$$$. For example, $$$\{3, 2, 4, 1\}$$$ is a permutation of length $$$4$$$, but $$$\{3, 3, 1, 4\}$$$ and $$$\{2, 3, 4, 5\}$$$ are not.

Note that if there are multiple valid permutations, print any.

Input

The first line of input contains a single integer $$$T$$$ $$$(1 \le T \le 1000)$$$ — the number of testcases.

The only line of each testcase contains a single integer $$$N$$$ $$$(2 \le N \le 10^5)$$$ – the size of the permutation $$$P$$$.

It's guaranteed that the sum of $$$N$$$ over all testcases does not exceed $$$10^5$$$

Output

For each testcase, print in a separate line any permutation of length $$$N$$$ that is an Ammar-utiful permutation.

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

D. DBSucks-ugly Array
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Team DBSucks did a terrible performance testing this contest, they were pretty slow. They farmed all possible penalties. Here is a problem with credit to their shameful performance.

You will be given an array $$$A$$$ of $$$N$$$ elements and an integer $$$M$$$, count the number of integers $$$X$$$ $$$(1 \le X \le M)$$$ that are co-prime with all elements of the array.

Note that: two integers are said to be co-prime if their greatest common divisor is $$$1$$$.

Input

The first line of input contains a single integer $$$T$$$ $$$(1 \le T \le 1000)$$$ — the number of testcases. Each testcase contains two lines.

The first line of each testcase contains a two integers $$$N$$$ and $$$M$$$ $$$(1 \le N$$$, $$$M \le 10^5)$$$ — the size of the array $$$A$$$ and the number $$$M$$$.

The second line of each testcase contains $$$N$$$ space-separated integers $$$A_1, A_2, \dots, A_N$$$ $$$(1 \le A_i \le 10^5)$$$ — the values of the array $$$A$$$.

It's guaranteed that the sum of $$$N$$$ and the sum of $$$M$$$ over all testcases does not exceed $$$10^5$$$

Output

For each testcase print a single integer — the number of integers that are co-prime with all elements of the array.

Example
Input
1
3 5
1 2 3
Output
2

E. Tareq-utiful Tree
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Tareq is not just known for his technique "The Blender of Standards", he is also known for his famous sentence: "I'll be back after I heat the water jug", where he won't be back until at least 2 months later. so he proposed this problem and said his famous sentence and the other judges had to actually prepare the problem for the contest

We define a colored tree to be a Tareq-utiful Tree if it can be split into two trees, and both trees have the same multiset of colors. In other words, the frequency of each color $$$c$$$ $$$(1 \le c \le N)$$$ is equal in both formed trees.

Splitting a tree into two trees is equivalent to choosing an edge and removing it from the tree.

Given a tree of $$$N$$$ vertices, where each vertex has a color $$$C_i$$$. In one operation, you can:

  • choose any two vertices $$$u$$$ and $$$v$$$ and exchange their colors, i.e. swap$$$(C_u, C_v)$$$.

Find the minimum number of operations you need to do, so that the tree becomes a Tareq-utiful Tree, Or report that it's impossible.

Input

The first line of the input contains a single integer $$$T$$$ $$$(1 \le T \le 1000)$$$ — the number of testcases.

The first line of each testcase contains a single integer $$$N$$$ $$$(2 \le N \le 2\cdot 10^5)$$$ — The number of vertices in the tree.

The second line of each testcase contains $$$N$$$ space-separated integers $$$C_1, C_2, \dots, C_N$$$ $$$(1 \le C_i \le N)$$$ — the colors of the vertices.

The next $$$N - 1$$$ lines contain the edges of the tree. Each line contains two integers $$$U$$$ and $$$V$$$ denoting an edge between vertices $$$U$$$ and $$$V$$$ $$$(1 \le U , V \le N , U \ne V)$$$. It is guaranteed that these edges form a tree.

It's guaranteed that the sum of $$$N$$$ over all testcases does not exceed $$$2\cdot 10^5$$$

Output

For each testcase print a single integer representing the minimum number of operations needed to make a Tareq-utiful Tree, or $$$-1$$$ if it is impossible.

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

F. Resli-utiful Pair
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Resli is never satisfied with only one problem, so here is another problem prepared for you by Resli.

We define a pair of integers $$$(a, b)$$$ to be a Resli-utiful Pair if it holds that:

  • $$$a^b \equiv 1 \bmod N$$$.
  • $$$a^b$$$ is a perfect square.
  • $$$2 \le a \le 2 \cdot 10^9$$$.
  • $$$2 \le b \le 2 \cdot 10^9$$$.

A perfect square is a positive integer that is obtained by multiplying an integer by itself, i.e. $$$4$$$ is a perfect square because it is obtained from $$$2 \times 2$$$, but $$$6$$$ is not.

Your task is easy. Given $$$N$$$, find any Resli-utiful Pair. It's guaranteed that the answer always exist.

Input

The first line of input contains a single integer $$$T$$$ $$$(1 \le T \le 10^5)$$$ — the number of testcases.

The only line of each testcase contains a single integer $$$N$$$ $$$(2 \le N \le 10^9)$$$ — the integer $$$N$$$.

Output

For each testcase, print in a separate line two space-separated integers $$$a$$$ and $$$b$$$ that are a Resli-utiful Pair.

Example
Input
1
2
Output
5 2

G. Wael-utiful Array
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Wael is known for his Telegram bio "We Travel Across the Horizons of Beauty", which actually reflects the problems he comes up with. They are always about maximizing, , you guessed it, the Beauty, or as he calls it, the Wael-uty.

Wael defines the Wael-uty of two unordered integers $$$(X,$$$ $$$Y)$$$ as the number of pairs of integers $$$(i, j)$$$ such that:

  • $$$1 \le i \le X$$$.
  • $$$1 \le j \le Y$$$.
  • $$$(i + j)$$$ is a perfect square

Well, according to Wael, Wael-uty is not only about pairs, it can also be found within arrays. Wael defines an array $$$B$$$ of length $$$M$$$ to be Wael-utiful if it holds that for any index $$$i$$$ such that $$$1 \le i \lt M$$$:

  • $$$(B_i + B_{i + 1})$$$ is a perfect square.

You will be given an array $$$A$$$ of length $$$N$$$. You need to find a Wael-utiful subset $$$B$$$ of elements of $$$A$$$ such that the sum of Wael-uty of each two adjacent elements is maximum possible.

A perfect square is a positive integer that is obtained by multiplying an integer by itself, i.e. $$$4$$$ is a perfect square because it is obtained from $$$2 \times 2$$$, but $$$6$$$ is not.

Note that:

  • an array $$$U$$$ is said to be a subset of array $$$V$$$, if $$$U$$$ can be obtained from $$$V$$$ by deletion of several (possibly zero or all) elements.
  • the elements of any chosen subset must be taken in their original order in array $$$A$$$.
Input

The first line of input contains a single integer $$$T$$$ $$$(1 \le T \le 2 \cdot 10^4)$$$ — the number of testcases. Each testcase contains two lines.

The first line of each testcase contains a single integer $$$N$$$ $$$(1 \le N \le 2 \cdot 10^5)$$$ — the length of the array $$$A$$$.

The second line of each testcase contains $$$N$$$ space-separated integers $$$A_1, A_2, \dots, A_N$$$ $$$(1 \le A_i \le 10^5)$$$ — the values in array $$$A$$$.

It's guaranteed that the sum of $$$N$$$ over all testcases does not exceed $$$2 \cdot 10^5$$$

Output

For each testcase print a single integer — the maximum possible sum of Wael-uty of a Wael-utiful subset $$$B$$$ of $$$A$$$.

Example
Input
4
6
4 12 3 4 12 3
6
4 25 11 25 11 3
3
1 2 3
3
1 7 4
Output
24
102
1
0

H. Ammar-utiful Array
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ammar does not know how to set problems. Therefore, Coach Khaled felt pitty about Ammar and decided to put his name on one of his problems, which is this problem.

We define an array of $$$M$$$ integers to be called an Ammar-utiful Array of Ammar-uty $$$X$$$ if the sum of all of its elements is less than or equal to $$$X$$$.

Ammar will give you $$$N$$$ elements, such that each element $$$i$$$ is associated with value $$$A_i$$$ and color $$$C_i$$$. You need to process $$$Q$$$ queries of the following forms:

  • $$$1 \; Col \; X$$$: For each element $$$i$$$ $$$(1 \le i \le N)$$$ such that $$$C_i \ne Col$$$, increase $$$A_i$$$ by $$$X$$$.
  • $$$2 \; Col \; Y$$$: Consider an array $$$B$$$ that consists of elements with color equal to $$$Col$$$, in the same original order that they appeared in array $$$A$$$. What is the length of the longest prefix $$$P$$$ (the prefix can be empty) of $$$B$$$ such that $$$P$$$ is an Ammar-utiful Array of Ammar-uty $$$Y$$$. (It is guaranteed that there is at least one element whose color is equal to $$$Col$$$).
Input

The first line of the input contains two integers $$$N$$$ $$$(1 \le N \le 2\cdot 10^5)$$$.

The second line of the input contains $$$N$$$ space-separated integers $$$A_1, A_2, \cdots, A_N$$$ $$$(1 \le A_i \le 2 \cdot 10^5)$$$ — the values associated with the elements.

The third line of the input contains $$$N$$$ space-separated integers $$$C_1, C_2, \cdots, C_N$$$ $$$(1 \le C_i \le 2 \cdot 10^5)$$$ — the colors associated with the elements.

The next line of the input contains an integer $$$Q$$$ $$$(1 \le Q \le 2\cdot 10^5)$$$.

Each line of the next $$$Q$$$ lines contains three integers describing the queries.

  • $$$1 \; Col \; X$$$: $$$(1 \le Col \le 2\cdot 10^5)$$$ $$$(1 \le X \le 10^5)$$$ — the query of the first type.
  • $$$2 \; Col \; Y$$$: $$$(1 \le Col \le 2\cdot 10^5)$$$ $$$(1 \le Y \le 10^{15})$$$ — the query of the second type (It is guaranteed that there is at least one element whose color is equal to $$$Col$$$).
Output

For each query of the second type, print a single line containing the length of the longest prefix $$$P$$$ of $$$B$$$ such that $$$P$$$ is an Ammar-utiful Array of Ammar-uty Y.

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

I. Obada-utiful Graph
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Obada is Osama's brother, and a former teammate of Tareq too. Do you know what that means? You guessed it, the Blender of Standards again. Obada is a bit smarter than Osama. He can make problems using the Blender that does not actually look like a Blender problem.

Obada will give you an Obada-utiful Graph. It's a graph that is given in a weird way.

It's an undirected graph with $$$N$$$ vertices given as a permutation $$$P$$$ such that there is an undirected edge between vertices $$$u$$$ and $$$v$$$ if:

  • $$$u \lt v$$$ and $$$P_u \lt P_v$$$.
Obada asks you $$$Q$$$ queries. Each query contains two integers $$$(i, j)$$$ that you have to:
  1. swap $$$(P_i,P_j)$$$.
  2. update the graph structure with correspondence to the update in permutation $$$P$$$ (it might add/remove some edges).
  3. find the number of connected components in the graph.
Input

The first line of the input contains two integers $$$N$$$ and $$$Q$$$ ($$$1 \le N \le 10^5$$$), ($$$1 \le Q \le 10^5$$$) — the number of vertices in the graph and the number of queries.

The second line contains $$$N$$$ distinct integers $$$P_1, P_2, \dots, P_N$$$ $$$(1 \le P_i \le N)$$$ — the permutation $$$P$$$.

Each of the next $$$Q$$$ lines contain two integers $$$i$$$ and $$$j$$$ $$$(1 \le i \lt j \le N)$$$ — the description of the queries.

Output

For each query print a single line — the number of connected components in the graph after the first $$$i$$$ queries.

Example
Input
3 2
1 2 3
1 3
2 3
Output
3
2
Note

Sample explanation:

  1. Initially the graph contains one connected component (there are edges between $$$(1, 2)$$$, $$$(1, 3)$$$ and $$$(2, 3)$$$).
  2. After the first query, the graph contains no edges, and thus it contains three connected components.
  3. After the second query, the graph contains one edge between $$$1$$$ and $$$2$$$, and thus it contains two connected components $$$\{1, 2\}$$$ and $$$\{3\}$$$.

J. Elias-utiful Array
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Elias is known for his love of standard problems. He achieves top rank in competitions of standard well-known problems. Moreover, he can only come up with standard problems. Here is his standard problem for this competition.

We define an array $$$B$$$ of $$$M$$$ integers to be called an Elias-utiful Array if it holds that for every pair of indices $$$(i, j)$$$ such that $$$(1 \le i \lt j \le N)$$$:

  • $$$B_i \& B_j \ge B_i \oplus B_j$$$

You're given an array $$$A$$$ of size $$$N$$$, you need to find the maximum possible length of some subset $$$S$$$ of $$$A$$$ that makes an Elias-utiful Array.

An array $$$U$$$ is said to be a subset of array $$$V$$$, if $$$U$$$ can be obtained from $$$V$$$ by deletion of several (possibly zero or all) elements.

Note that:

  • & represents the bitwise AND operation. The bitwise AND is a binary operation that takes two bit patterns of equal length and performs the logical AND operation on each pair of corresponding bits. The result in each position is $$$1$$$ if both bits are $$$1$$$, otherwise the result is $$$0$$$. For example: $$$0101$$$ $$$($$$decimal $$$5)$$$ AND $$$0011$$$ $$$($$$decimal $$$3)$$$ $$$=$$$ $$$0001$$$ $$$($$$decimal $$$1)$$$.
  • $$$\oplus$$$ represents the bitwise XOR operation. The bitwise XOR is a binary operation that takes two bit patterns of equal length and performs the logical exclusive OR operation on each pair of corresponding bits. The result in each position is $$$1$$$ if both bits are different, otherwise the result is $$$0$$$. For example: $$$0101$$$ $$$($$$decimal $$$5)$$$ XOR $$$0011$$$ $$$($$$decimal $$$3)$$$ $$$=$$$ $$$0110$$$ $$$($$$decimal $$$6)$$$.
Input

The first line of input contains a single integer $$$T$$$ $$$(1 \le T \le 1000)$$$ — the number of testcases. Each testcase contains two lines.

The first line of each testcase contains a single integer $$$N$$$ $$$(1 \le N \le 10^5)$$$ — the size of the array $$$A$$$.

The second line of each testcase contains $$$N$$$ space-separated integers $$$A_1, A_2, \dots, A_N$$$ $$$(1 \le A_i \lt 2^{30})$$$ — the values of the array $$$A$$$.

It's guaranteed that the sum of $$$N$$$ over all testcases does not exceed $$$10^5$$$

Output

For each testcase print a single integer — the maximum possible length of some subset that makes an Elias-utiful Array.

Example
Input
3
6
8 6 2 7 2 5
3
1 10 100
2
8 12
Output
3
1
2
Note

In the first testcase, the subset that has the maximum length is $$$\{6, 7, 5\}$$$.

K. Damas-utiful vs Aleppo-utiful
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Judges worked so hard to prepare a good problemset for Damascus and Aleppo contestants because they knew how delicious the food is in these cities.

Judges split themselves into two teams, with one team going to Damascus while the other team is going to Aleppo. They bet on the city with the most delicious food. Your task is to determine which team was actually right?

If you believe that food in Damascus is better, then print the most delicious food you have ever tried in Damascus. Otherwise, if you believe that food in Aleppo is better, then print the most delicious food you have ever tried there.

Moreover, if you don't really care about this silly bet, just print "M7ashe" as it is the only food both teams agree to be the best food ever.

Input

What is your favourite food?

Output

Print the best food you have ever tried, or just print "M7ashe"

Example
Input
What is your favorite food?
Output
M7ashe

L. Khaled-utiful Vertices
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Khaled is well known for his love of trees, and for the tree problems he can come up with. However, he is tired of all his problems being solved every time, so he decided to come up with a tree problem that no body can solve.

Khaled will give you a tree of $$$N$$$ vertices, such that each vertex $$$i$$$ is associated with value $$$A_i$$$, and vertex $$$1$$$ is the root vertex of the tree.

We call some chosen set of vertices of the given tree a Khaled-utiful Set of Beauty $$$K$$$ if it holds that for every chosen vertex $$$v$$$:

  • Vertex $$$v$$$ has at most $$$K-1$$$ chosen ancestors in the given tree.

We define $$$F(K)$$$ as the maximum possible sum of values of some Khaled-utiful Set of Beauty $$$K$$$ of the given tree. You need to find $$$F(K)$$$ for all $$$K$$$ $$$(1 \le K \le N)$$$.

Input

The first line of the input contains a single integer $$$T$$$ ($$$1 \le T \le 1000$$$) — the number of testcases.

The first line of each testcase contains a single integer $$$N$$$ $$$(2 \le N \le 2 \cdot 10^5)$$$ — the number of vertices in the tree.

The second line of each testcase contains $$$N$$$ space-separated integers $$$A_1, A_2, \dots, A_N$$$ $$$(1 \le A_i \le 10^9)$$$ — the values associated with the nodes.

The following $$$N - 1$$$ lines contain the edges of the tree. Each line contains two integers $$$U$$$ and $$$V$$$ denoting an edge between vertices $$$U$$$ and $$$V$$$ $$$(1 \le U , V \le N , U \ne V)$$$. It is guaranteed that these edges form a tree.

It's guaranteed that the sum of $$$N$$$ over all testcases does not exceed $$$2 \cdot 10^5$$$

Output

For each testcase print a single line containing $$$N$$$ space-separated integers $$$S_1, S_2, \dots, S_N$$$, where the $$$S_i$$$ represents the value of $$$F(i)$$$.

Example
Input
2
4
1 2 3 4
1 2
1 3
2 4
2
100 1
1 2
Output
7 9 10 10 
100 101

M. Resli-utiful Indices
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Resli is a contestant, judge, system and administrator. He can do literally everything, but can he come up with good problems? Here is Resli's problem for you.

We define an index $$$i$$$ of some permutation $$$P$$$ to be a Resli-utiful index if it holds that $$$P_i \gt P_{i + 1}$$$.

You will be building a permutation $$$P$$$ of length $$$N$$$. You will be given a set $$$S$$$ of $$$K$$$ distinct integers, that represents some specific indices of permutation $$$P$$$.

You need to count the number of permutations $$$P$$$ of length $$$N$$$, such that for every Resli-utiful index $$$i$$$ of $$$P$$$, it holds that:

  • $$$i$$$ belongs to $$$S$$$. In other words, there exists some index $$$j$$$ such that $$$S_j = i$$$.

Find the answer, and print it modulo $$$10^9 + 7$$$.

Input

The first line of input contains a single integer $$$T$$$ $$$(1 \le T \le 1000)$$$ — the number of testcases. Each testcase contains two lines.

The first line of each testcase contains two integers $$$N$$$ and $$$K$$$ $$$(2 \le N \le 2\cdot 10^5$$$, $$$1 \le K \lt N)$$$.

The second line of each testcase contains $$$K$$$ space-separated integers $$$S_1, S_2, \dots, S_K$$$ $$$(1 \le S_i \lt N)$$$ — the specific indices of $$$P$$$.

It's guaranteed that the sum of $$$K$$$ over all testcases does not exceed $$$2\cdot 10^5$$$

Output

For each testcase print a single integer — the number of permutations $$$P$$$ that satisfy the condition, modulo $$$10^9+7$$$.

Example
Input
3
2 1
1
3 2
1 2
3 1
2
Output
2
6
3