Codeforces Round 873 (Div. 1)
A. Counting Orders
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two arrays $$$a$$$ and $$$b$$$ each consisting of $$$n$$$ integers. All elements of $$$a$$$ are pairwise distinct.

Find the number of ways to reorder $$$a$$$ such that $$$a_i \gt b_i$$$ for all $$$1 \le i \le n$$$, modulo $$$10^9 + 7$$$.

Two ways of reordering are considered different if the resulting arrays are different.

Input

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^{5}$$$) — the length of the array $$$a$$$ and $$$b$$$.

The second line of each test case contains $$$n$$$ distinct integers $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the array $$$a$$$. It is guaranteed that all elements of $$$a$$$ are pairwise distinct.

The second line of each test case contains $$$n$$$ integers $$$b_1$$$, $$$b_2$$$, $$$\ldots$$$, $$$b_n$$$ ($$$1 \le b_i \le 10^9$$$) — the array $$$b$$$.

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

Output

For each test case, output the number of ways to reorder array $$$a$$$ such that $$$a_i \gt b_i$$$ for all $$$1 \le i \le n$$$, modulo $$$10^9 + 7$$$.

Example
Input
5
6
9 6 8 4 5 2
4 1 5 6 3 1
3
4 3 2
3 4 9
1
2
1
3
2 3 4
1 3 3
12
2 3 7 10 23 28 29 50 69 135 420 1000
1 1 2 3 5 8 13 21 34 55 89 144
Output
32
0
1
0
13824

B1. Range Sorting (Easy Version)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The only difference between this problem and the hard version is the constraints on $$$t$$$ and $$$n$$$.

You are given an array $$$a$$$, consisting of $$$n$$$ distinct integers $$$a_1, a_2, \ldots, a_n$$$.

Define the beauty of an array $$$p_1, p_2, \ldots p_k$$$ as the minimum amount of time needed to sort this array using an arbitrary number of range-sort operations. In each range-sort operation, you will do the following:

  • Choose two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \lt r \le k$$$).
  • Sort the subarray $$$p_l, p_{l + 1}, \ldots, p_r$$$ in $$$r - l$$$ seconds.

Please calculate the sum of beauty over all subarrays of array $$$a$$$.

A subarray of an array is defined as a sequence of consecutive elements of the array.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 5 \cdot 10^3$$$). The description of the test cases follows.

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

The second line of each test case consists of $$$n$$$ integers $$$a_1,a_2,\ldots, a_n$$$ ($$$1\le a_i\le 10^9$$$). It is guaranteed that all elements of $$$a$$$ are pairwise distinct.

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

Output

For each test case, output the sum of beauty over all subarrays of array $$$a$$$.

Example
Input
5
2
6 4
3
3 10 6
4
4 8 7 2
5
9 8 2 4 6
12
2 6 13 3 15 5 10 8 16 9 11 18
Output
1
2
8
16
232
Note

In the first test case:

  • The subarray $$$[6]$$$ is already sorted, so its beauty is $$$0$$$.
  • The subarray $$$[4]$$$ is already sorted, so its beauty is $$$0$$$.
  • You can sort the subarray $$$[6, 4]$$$ in one operation by choosing $$$l = 1$$$ and $$$r = 2$$$. Its beauty is equal to $$$1$$$.
The sum of beauty over all subarrays of the given array is equal to $$$0 + 0 + 1 = 1$$$.

In the second test case:

  • The subarray $$$[3]$$$ is already sorted, so its beauty is $$$0$$$.
  • The subarray $$$[10]$$$ is already sorted, so its beauty is $$$0$$$.
  • The subarray $$$[6]$$$ is already sorted, so its beauty is $$$0$$$.
  • The subarray $$$[3, 10]$$$ is already sorted, so its beauty is $$$0$$$.
  • You can sort the subarray $$$[10, 6]$$$ in one operation by choosing $$$l = 1$$$ and $$$r = 2$$$. Its beauty is equal to $$$2 - 1 = 1$$$.
  • You can sort the subarray $$$[3, 10, 6]$$$ in one operation by choosing $$$l = 2$$$ and $$$r = 3$$$. Its beauty is equal to $$$3 - 2 = 1$$$.
The sum of beauty over all subarrays of the given array is equal to $$$0 + 0 + 0 + 0 + 1 + 1 = 2$$$.

B2. Range Sorting (Hard Version)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The only difference between this problem and the easy version is the constraints on $$$t$$$ and $$$n$$$.

You are given an array $$$a$$$, consisting of $$$n$$$ distinct integers $$$a_1, a_2, \ldots, a_n$$$.

Define the beauty of an array $$$p_1, p_2, \ldots p_k$$$ as the minimum amount of time needed to sort this array using an arbitrary number of range-sort operations. In each range-sort operation, you will do the following:

  • Choose two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \lt r \le k$$$).
  • Sort the subarray $$$p_l, p_{l + 1}, \ldots, p_r$$$ in $$$r - l$$$ seconds.

Please calculate the sum of beauty over all subarrays of array $$$a$$$.

A subarray of an array is defined as a sequence of consecutive elements of the array.

Input

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

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

The second line of each test case consists of $$$n$$$ integers $$$a_1,a_2,\ldots, a_n$$$ ($$$1\le a_i\le 10^9$$$). It is guaranteed that all elements of $$$a$$$ are pairwise distinct.

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

Output

For each test case, output the sum of beauty over all subarrays of array $$$a$$$.

Example
Input
5
2
6 4
3
3 10 6
4
4 8 7 2
5
9 8 2 4 6
12
2 6 13 3 15 5 10 8 16 9 11 18
Output
1
2
8
16
232
Note

In the first test case:

  • The subarray $$$[6]$$$ is already sorted, so its beauty is $$$0$$$.
  • The subarray $$$[4]$$$ is already sorted, so its beauty is $$$0$$$.
  • You can sort the subarray $$$[6, 4]$$$ in one operation by choosing $$$l = 1$$$ and $$$r = 2$$$. Its beauty is equal to $$$1$$$.
The sum of beauty over all subarrays of the given array is equal to $$$0 + 0 + 1 = 1$$$.

In the second test case:

  • The subarray $$$[3]$$$ is already sorted, so its beauty is $$$0$$$.
  • The subarray $$$[10]$$$ is already sorted, so its beauty is $$$0$$$.
  • The subarray $$$[6]$$$ is already sorted, so its beauty is $$$0$$$.
  • The subarray $$$[3, 10]$$$ is already sorted, so its beauty is $$$0$$$.
  • You can sort the subarray $$$[10, 6]$$$ in one operation by choosing $$$l = 1$$$ and $$$r = 2$$$. Its beauty is equal to $$$2 - 1 = 1$$$.
  • You can sort the subarray $$$[3, 10, 6]$$$ in one operation by choosing $$$l = 2$$$ and $$$r = 3$$$. Its beauty is equal to $$$3 - 2 = 1$$$.
The sum of beauty over all subarrays of the given array is equal to $$$0 + 0 + 0 + 0 + 1 + 1 = 2$$$.

C. Palindrome Partition
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A substring is a continuous and non-empty segment of letters from a given string, without any reorders.

An even palindrome is a string that reads the same backward as forward and has an even length. For example, strings "zz", "abba", "abccba" are even palindromes, but strings "codeforces", "reality", "aba", "c" are not.

A beautiful string is an even palindrome or a string that can be partitioned into some smaller even palindromes.

You are given a string $$$s$$$, consisting of $$$n$$$ lowercase Latin letters. Count the number of beautiful substrings of $$$s$$$.

Input

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 5\cdot 10^5$$$).

The second line of each test case contains a string $$$s$$$. String $$$s$$$ consists of only lowercase Latin letters and has a length of $$$n$$$.

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

Output

For each test case print the number of beautiful substrings.

Example
Input
6
6
abaaba
1
a
2
aa
6
abcdef
12
accabccbacca
6
abbaaa
Output
3
0
1
0
14
6
Note

In the first test case, the beautiful substrings are "abaaba", "baab", "aa".

In the last test case, the beautiful substrings are "aa" (counted twice), "abba", "bb", "bbaa", "abbaaa".

D. Two Centroids
time limit per test
1.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a tree (an undirected connected acyclic graph) which initially only contains vertex $$$1$$$. There will be several queries to the given tree. In the $$$i$$$-th query, vertex $$$i + 1$$$ will appear and be connected to vertex $$$p_i$$$ ($$$1 \le p_i \le i$$$).

After each query, please find out the least number of operations required to make the current tree has two centroids. In one operation, you can add one vertex and one edge to the tree such that it remains a tree.

A vertex is called a centroid if its removal splits the tree into subtrees with at most $$$\lfloor \frac{n}{2} \rfloor$$$ vertices each, with $$$n$$$ as the number of vertices of the tree. For example, the centroid of the following tree is $$$3$$$ because the biggest subtree after removing the centroid has $$$2$$$ vertices.

In the next tree, vertex $$$1$$$ and $$$2$$$ are both centroids.

Input

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

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 5 \cdot 10^{5}$$$) — the number of nodes of the final tree.

The second line of each test case contains $$$n - 1$$$ integers $$$p_1, p_2, \ldots, p_{n - 1}$$$ ($$$1 \le p_i \le i$$$) — the index of the vertex that is connected to vertex $$$i + 1$$$.

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

Output

For each test case, output $$$n - 1$$$ integers. The $$$i$$$-th integer is the answer to the $$$i$$$-th query — the least number of operations required to make the current tree have two centroids.

We can show that an answer always exists.

Example
Input
5
2
1
3
1 1
4
1 2 3
7
1 2 3 2 5 2
10
1 2 2 4 5 5 7 8 9
Output
0
0 1
0 1 0
0 1 0 1 2 3
0 1 2 1 0 1 0 1 2
Note

The illustrations below are of the fourth example test case.

After the third query:

The tree already has vertices $$$2$$$ and $$$3$$$ as centroids, so no operations are needed.

After the fourth query:

Adding vertex $$$x$$$ to the tree makes vertices $$$2$$$ and $$$3$$$ centroids. Only one operation is needed.

After the fifth query:

Adding vertex $$$x$$$ and $$$y$$$ to the tree makes vertices $$$5$$$ and $$$2$$$ centroids. Two operations are needed.

After the sixth query:

Adding vertex $$$x$$$, $$$y$$$, and $$$z$$$ to the tree makes vertices $$$5$$$ and $$$2$$$ centroids. Three operations are needed.

E. Bus Routes
time limit per test
2.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

There is a country consisting of $$$n$$$ cities and $$$n - 1$$$ bidirectional roads connecting them such that we can travel between any two cities using these roads. In other words, these cities and roads form a tree.

There are $$$m$$$ bus routes connecting the cities together. A bus route between city $$$x$$$ and city $$$y$$$ allows you to travel between any two cities in the simple path between $$$x$$$ and $$$y$$$ with this route.

Determine if for every pair of cities $$$u$$$ and $$$v$$$, you can travel from $$$u$$$ to $$$v$$$ using at most two bus routes.

Input

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

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 5 \cdot 10^5, 0 \le m \le 5 \cdot 10^5$$$) — the number of cities and the number of bus routes.

Then $$$n - 1$$$ lines follow. Each line contains two integers $$$u$$$ and $$$v$$$ denoting a road connecting city $$$u$$$ and city $$$v$$$ ($$$1 \le u, v \le n, u \neq v$$$). It is guaranteed that these cities and roads form a tree.

Then $$$m$$$ lines follow. Each line contains two integers $$$x$$$ and $$$y$$$ denoting a bus route between city $$$x$$$ and city $$$y$$$ ($$$1 \le x, y \le n$$$).

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

Output

For each test case, output "YES" if you can travel between any pair of cities using at most two bus routes.

Otherwise, output "NO". In the next line, output two cities $$$x$$$ and $$$y$$$ ($$$1 \le x, y \le n$$$) such that it is impossible to reach city $$$y$$$ from city $$$x$$$ using at most two bus routes.

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 2
1 2
2 3
3 4
2 5
1 4
5 2
5 1
1 2
2 3
3 4
2 5
1 5
2 0
1 2
6 3
1 2
2 3
3 4
4 5
5 6
1 3
2 5
4 6
Output
YES
NO
1 3
NO
1 2
NO
1 6
Note

Here are the graphs of test case $$$1$$$, $$$2$$$, and $$$4$$$:

Sample 1
Sample 2
Sample 4

F. Copium Permutation
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a permutation $$$a_1,a_2,\ldots,a_n$$$ of the first $$$n$$$ positive integers. A subarray $$$[l,r]$$$ is called copium if we can rearrange it so that it becomes a sequence of consecutive integers, or more formally, if $$$$$$\max(a_l,a_{l+1},\ldots,a_r)-\min(a_l,a_{l+1},\ldots,a_r)=r-l$$$$$$ For each $$$k$$$ in the range $$$[0,n]$$$, print out the maximum number of copium subarrays of $$$a$$$ over all ways of rearranging the last $$$n-k$$$ elements of $$$a$$$.

Input

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

The first line of each test case contains a single integer $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$). It is guaranteed that the given numbers form a permutation of length $$$n$$$.

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

Output

For each test case print $$$n+1$$$ integers as the answers for each $$$k$$$ in the range $$$[0,n]$$$.

Example
Input
5
5
5 2 1 4 3
4
2 1 4 3
1
1
8
7 5 8 1 4 2 6 3
10
1 4 5 3 7 8 9 2 10 6
Output
15 15 11 10 9 9 
10 8 8 7 7 
1 1 
36 30 25 19 15 13 12 9 9 
55 55 41 35 35 25 22 22 19 17 17
Note

In the first test case, the answer permutations for each $$$k$$$ are $$$[1,2,3,4,5]$$$, $$$[5,4,3,2,1]$$$, $$$[5,2,3,4,1]$$$, $$$[5,2,1,3,4]$$$, $$$[5,2,1,4,3]$$$, $$$[5,2,1,4,3]$$$.

In the second test case, the answer permutations for each $$$k$$$ are $$$[1,2,3,4]$$$, $$$[2,1,3,4]$$$, $$$[2,1,3,4]$$$, $$$[2,1,4,3]$$$, $$$[2,1,4,3]$$$.