Tishreen Collegiate Programming Contest 2024
A. Gym Tournament
time limit per test
2 s
memory limit per test
256 megabytes
input
standard input
output
standard output

After the last tournament that Yaman participated in, he gained some experience that he will use in the next tournament.

The gym in which he exercises has $$$n$$$ barbell plates numbered from $$$1$$$ to $$$n$$$, and the weight of the $$$i$$$-th plate is $$$a_i$$$ and its width is $$$b_i$$$.

Yaman will train on an exercise that uses a bar with two sides, so he will choose two disjoint subsets from the $$$n$$$ plates, one for each side.

Yaman's coach has a balancing function $$$f$$$ that takes the subset of each side and returns the balancing value.

Assuming that the left side subset is $$$l$$$ and it contains $$$cnt_l$$$ numbers $$$[l_1, l_2, .., l_{cnt_l}]$$$ which represent the indices of the left side subset, and the right side subset is $$$r$$$ and it contains $$$cnt_r$$$ numbers $$$[r_1, r_2, .., r_{cnt_r}]$$$ which represent the indices of the right side subset, then the function $$$f$$$ is:

$$$$$$f(l, r) = | ( \sum_{i = 1}^{cnt_l}(b_{l_i}) - \sum_{i = 1}^{cnt_r} (b_{r_i}) ) |$$$$$$

The coach wants to test Yaman on $$$q$$$ tests, each one has two numbers $$$L$$$, $$$R$$$, and he wants to know the maximum total weight of both sides that Yaman can lift if the value of the balancing function $$$f$$$ is between $$$[L, R]$$$ inclusive.

Help Yaman's coach to determine the maximum weight for each test or print $$$0$$$ if he can't achieve the wanted balancing value.

Input

The first line contains the number of test cases $$$t$$$ $$$( 1 \le t \le 10^{5} )$$$. A description of the test cases follows.

The first line of each test case contains two integers $$$n$$$, $$$q$$$ $$$( 1 \le n \le 10^{5} )$$$, $$$( 1 \le q \le 10^{6} )$$$ — the number of barbell plates in the gym, and the number of tests respectively.

The second line contains $$$n$$$ integers $$$a_1, a_2, .., a_n$$$ $$$( 1 \le a_i \le 10^{9} )$$$ — the weights of the barbell plates.

The third line contains $$$n$$$ integers $$$b_1, b_2, .., b_n$$$ $$$( 1 \le b_i \le 10^{5} )$$$ — the width of the barbell plates.

The next $$$q$$$ lines contain two integers $$$L_i$$$, $$$R_i$$$ $$$( 1 \le L_i \le R_i \le 10^{5} )$$$ — the range of the value of the balancing function in the $$$i$$$-th test.

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

And it is guaranteed that the sum of $$$b_i$$$ over all test cases does not exceed $$$10^{5}$$$.

And it is guaranteed that the sum of $$$q$$$ over all test cases does not exceed $$$10^{6}$$$.

Output

Print the maximum weight for each test or print $$$0$$$ if he can't achieve the wanted balancing value.

Example
Input
1
5 4
5 2 3 2 5
1 4 9 12 20
1 2
7 7
99 100
3 3
Output
17
12
0
14

B. Broken String
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a string $$$s$$$ consisting of $$$n$$$ digits.

You can do the following operation as many times as you want:

Choose one digit and increase it by $$$1$$$ (if it isn't $$$9$$$) or decrease it by $$$1$$$ (if it isn't $$$0$$$).

You have to make the string palindrome (i.e. $$$s[i] = s[n-i+1]$$$ for every $$$i$$$: $$$1 \le i \le n$$$) using the minimum number of operations.

Input

The first line contains an integer $$$t$$$ $$$(1 \le t \le 10^{3})$$$ , the number of testcases.

Every testcase consists of one string $$$s$$$ $$$(1 \le |s| \le 10^{3})$$$.

It's guaranteed that the sum of $$$|s|$$$ over all testcases doesn't exceed $$$10^3$$$.

Output

For every test case, you have to print the minimum number of operations needed to make the string palindrome.

Example
Input
3
123456789
2222
89478345
Output
20
0
10

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

George and Mohamed want to get in shape, so George tells Mohamed, "Lets go leafilians," "a type of person who only eats leaves".

They found a delicious tree (undirected connected graph with $$$n$$$ nodes and $$$n-1$$$ edges).

They start eating in turns. George starts eating first. In each turn to get full, the one who eats will do one of these two operations:

  1. Eat all leaves of the tree.
  2. Save one of the leaves and eat the rest.

The one who can't eat a leaf at the end will go eat Shawarma and lose.

A leaf node is a node with degree less than or equal to 1.

Can you tell us who will win and stay leafilians?

Input

The first line contains the number of test cases $$$t$$$ $$$( 1 \le t \le 10^{5} )$$$. A description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ $$$( 1 \le n \le 10^{5} )$$$ indicating the number of nodes in the tree.

The following $$$n-1$$$ lines of each test case describe the edges of the tree.The $$$i$$$-th of these lines contains two integers $$$u_i$$$ and $$$v_i$$$ $$$( 1 \le u_i , v_i \le n , u_i \not = v_i )$$$ the indices of the vertices connected by the $$$i$$$-th edge.

It is guaranteed that the given edges form a tree.

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

Output

For each test case, print "Go8" if George wins; otherwise, print "Neodoomer".

Example
Input
2
1
3
1 2
1 3
Output
Go8
Neodoomer

D. Lazy Jaber
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

One day Jaber found an array $$$a$$$ of size $$$n$$$. He wanted to count how many good subarrays are in this array.

Jaber considers a subarray $$$[a_l, a_{l+1}, .., a_r]$$$ good if he could choose a non-negative integer $$$x$$$ and after replacing each $$$a_i$$$ with $$$(a_i \oplus x)$$$ for each $$$i$$$ $$$(l \le i \le r)$$$ the resulting subarray $$$[a_l, a_{l+1}, .., a_r]$$$ becomes non-decreasing (where $$$\oplus$$$ is the bitwise XOR operation).

A subarray is the sequence of consecutive elements of the array.

A subarray $$$b$$$ of length $$$m$$$ is called non-decreasing if $$$b_i$$$ $$$\le$$$ $$$b_{i+1}$$$ for each $$$i$$$ such that $$$(1 \le i \lt m)$$$

As Jaber is too lazy and doesn't want to do any work today, he asks you to count this number for him.

Input

The first line contains a single integer $$$n$$$ $$$(1 \le n \le 10^6)$$$ — The size of the array.

The second line contains $$$n$$$ integers $$$a_1, a_2, ..., a_n$$$ $$$(1 \le a_i \le 10^9)$$$ — The array $$$a$$$.

Output

The number of good subarrays.

Examples
Input
3
2 1 2
Output
5
Input
5
5 2 1 4 7
Output
12
Input
8
4 2 2 3 6 2 1 4
Output
22

E. Sorting Cards
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Today is a great day at Uncling University. We have a new grand uncle! After two years of training at Uncleforces, Uncle Jaber has finally become a granduncle. He is very happy now!

There is a law at Uncling University: once you become a granduncle, you have to give a lecture about uncling.

As a troublemaker, Attal wants to ask a provocative question during the lecture. He will ask about a problem. Yes, he wants to discuss a problem from the last gym he participated in. Hosen is attending the lecture and he gets angry when someone discusses a problem from a gym. But if Jaber solves it before him, he will calm down and forget about it. You have to help Jaber solve the problem as fast as possible to avoid Hosen's rage.

Here is the problem:

We have an infinite number of playing cards, each card having a number between $$$1$$$ and $$$M$$$, and a color between $$$1$$$ and $$$K$$$.

You have to count the number of ways to choose a stack $$$A$$$ of $$$N$$$ cards such that the resulting stack $$$B$$$ is good.

Stack $$$B$$$ is obtained in the following way:

  1. Stack $$$B$$$ is initially empty.
  2. If stack $$$A$$$ is empty, we are done.
  3. Take the card from the top of stack $$$A$$$ and put it in your hand (then the card is removed from $$$A$$$).
  4. If stack $$$B$$$ is empty, put the card on the top of stack $$$B$$$. Otherwise, if the color of the card in your hand and the color of the card on the top of stack $$$B$$$ are different, then put the card in your hand on the top of stack $$$B$$$; otherwise, throw it away.
  5. Return to step 2.
Stack $$$B$$$ is good if the numbers written on the cards from the top to the bottom are sorted in non-decreasing order.

Two stacks of size $$$N$$$ are considered different if and only if there is an integer $$$i$$$ such that the $$$i_{th}$$$ card from the top in the first stack differs from the $$$i_{th}$$$ card from the top in the second one.

Two cards are considered different if they have different numbers or colors.

As the number may be very large, you are asked to print it modulo $$$10^9 + 7$$$.

Input

The first line of input contains a single $$$T$$$ $$$(1 \le T \le 10^5)$$$, the number of test cases.

Each of the next T lines contains three positive integers $$$N, M, K$$$ $$$(1 \le N,M,K \le 10^5)$$$, the size of the Stack $$$A$$$, the maximum number of a card, and the maximum color of a card respectively.

It is guaranteed that the sum of $$$N$$$ over all test cases doesn't exceed $$$10^5$$$.

Output

Output the number of ways to choose a stack $$$A$$$ of $$$N$$$ cards such that the resulting stack $$$B$$$ is good modulo $$$10^9 + 7$$$.

Example
Input
3
1 1 1
2 2 2
3 1 2
Output
1
14
8

F. We Want a Lesson
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Legend says that there was a coach at DCPC named Jaber. His account was new on all competitive programming sites because he camouflaged himself, but he was a very smart and kind person.

One of the ways he used to camouflage himself is that when someone achieved something, he said to them, "BdnaDars".

Coach Yaman developed a strategy to prevent Jaber from saying that phrase in the future. The strategy says that when Jaber says, "BdnaDars" we respond with "Enough!" and otherwise we respond with "OK".

Now Jaber wants to talk to you. Use Yaman's strategy by responding to him.

Input

The first line of the input contains one integer $$$n$$$ $$$( 1 \le n \le 10^{3} )$$$ — the number of phrases that Coach Jaber will say to you.

Each of the next $$$n$$$ lines contains one string $$$s_i$$$ $$$( 1 \le | s_i | \le 100)$$$ — the phrase of the $$$i$$$-th request. It's guaranteed that the string has only alphabet letters.

Output

For each phrase that Coach Jaber will say to you, print "Enough!" (without quotes), or print "OK" (without quotes), depending on Yaman's strategy.

Example
Input
2
Hi
BdnaDars
Output
OK
Enough!

G. Less is More
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a number $$$n$$$. Consider all pairs of natural numbers $$$a$$$ and $$$b$$$.

Your task is to find out how many distinct values of number $$$m$$$ satisfy the following equation:

$$$$$$ \forall (a, b) \in \mathbb{N}, (a+b)^n \equiv a^n + b^n \pmod m$$$$$$

Input

The first line contains a single integer number $$$(1 \le T \le 3 \times 10^5)$$$, the number of test cases.

Each test case contains a single integer $$$(2 \le n \le 10^6)$$$.

Output

You should print a single integer number (the distinct possible values of $$$m$$$ mod $$$1000000007$$$) for each testcase.

Example
Input
2
3
4
Output
4
2

H. Divide And Multiply
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Once upon a time, Attal was playing with an array and applying some operations on it. But during his playing, he noticed that he hates the array if it's elements are not the same.

Attal was a lazy man. So he gives Yaman the array $$$a$$$ that contains $$$n$$$ integers $$$[a_1, a_2, ... a_n]$$$, and he asks Yaman to make their elements equal using two kinds of operations:

  1. Choose an integer $$$i$$$ such that $$$1 \le i \le n$$$ and an integer number $$$k$$$, and replace $$$a_i$$$ with $$$k * a_i$$$.
  2. Choose an integer $$$i$$$ such that $$$1 \le i \le n$$$ and an integer number $$$k$$$ that divides $$$a_i$$$ and replace $$$a_i $$$ with $$$\frac{a_i}{k}$$$.

Note that the number $$$k$$$ can be different in each operation.

Yaman wants to make the array's elements equal using the minimum number of operations (possibly zero). Help Yaman to find it.

Input

The first line contains the number of test cases $$$t$$$ $$$( 1 \le t \le 10^{5} )$$$. A description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ $$$( 1 \le n \le 10^{6} )$$$, — the length of the array $$$a$$$.

The next line contains $$$n$$$ integers $$$a_i$$$ $$$( 1 \le a_i \le n)$$$, — the array $$$a$$$.

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

Output

Print the minimum number of operations needed to make the elements of the array $$$a$$$ equal.

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

I. The Math Guy
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Omar helps George prepare tests on polygons.

Now George is thrilled, so he gives Omar an array of size $$$n$$$ as a present, where each element $$$a_i$$$ is equal to $$$i$$$, starting from $$$1$$$ and ending at $$$n$$$.

As Omar is "The Math Guy" he immediately starts doing these operations on the array $$$n$$$ times in order:

  1. Remove the $$$\dagger$$$Median of the array.
  2. Add the $$$\ddagger$$$MEX of the array to his score.

Can you tell Omar his final score?

$$$\dagger$$$Median of the array is the element in position $$$\lceil \frac{n}{2} \rceil$$$ of the array. Median of $$$[1,2,3,4]$$$ is $$$2$$$ , Median of $$$[1,2,3]$$$ is $$$2$$$.

$$$\ddagger$$$MEX is the minimum positive number not present in the array. MEX of $$$[]$$$ is $$$1$$$, MEX of $$$[1,3,5]$$$ is $$$2$$$.

Input

The first line contains the number of test cases $$$t$$$ $$$( 1 \le t \le 10^{5} )$$$. A description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ $$$( 1 \le n \le 10^{9} )$$$ indicating the size of the array.

Output

For each test case print a single integer represents Omar's final score.

Example
Input
2
1
2
Output
1
2

J. F Less Than G
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Khaled is a bad boy, and he loves to rip papers. His father has got tired of him, and he wants to go on a trip with his friends, and your job is to take care of him.

Bad boy Khaled usually comes up with bad problems and wants people to solve them, and if they don't, he gets mad and starts ripping a lot of papers. He gives you this problem and wants you to solve it.

Given two arrays $$$a$$$ and $$$b$$$ of $$$n$$$ non-negative integers, count the number of good pairs $$$l$$$,$$$r$$$ $$$(1 \le l \le r \le n)$$$, satisfying $$$$$$F(l,r) \lt G(l,r)$$$$$$ Where $$$F(l,r)$$$ is the sum of the square of numbers in the range $$$[l,r]$$$ from the array $$$a$$$, more formally: $$$$$$F(l,r) = {\sum_{i = l}^r a_i^2}$$$$$$

And $$$G(l,r)$$$ is the square of the bitwise OR of the range $$$[l,r]$$$ from the array $$$b$$$, more formally:

$$$$$$ G(l,r) = (b_l | b_{l+1} | .... b_r)^2 $$$$$$

Where | is the bitwise OR operation. To prevent Khaled from ripping your papers, you have to solve his problem.

Input

The first line contains a single integer $$$n$$$ $$$(1 \le n \le 2*10^5)$$$, the length of the arrays $$$a$$$ and $$$b$$$.

The second line contains $$$n$$$ non-negative integers $$$a_1,....,a_n$$$ $$$(0 \le a_i \le 10^6)$$$.

The third line contains $$$n$$$ non-negative integers $$$b_1,....,b_n$$$ $$$(0 \le b_i \le 10^6)$$$.

Output

Output the number of good pairs

Examples
Input
1
2
3
Output
1
Input
2
1 6
3 4
Output
2
Input
5
1 2 4 3 1
1 4 8 7 1
Output
13

K. CP and GIT
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Once upon a time, in the world of algorithms and data structures, there lived a competitive programmer named Yaman. Armed with his trusty keyboard and an unwavering passion for programming, he decided to build a git repository containing a project that would serve as a reference for his code in the field of competitive programming.

The project he is working on contains $$$n$$$ files numbered from $$$1$$$ to $$$n$$$, and the name of the $$$i$$$-th file is $$$s_i$$$.

The repository contains a section called Stage that currently contains $$$m$$$ files from the project's files, and the rest of the files are located outside the Stage in a section called Workspace. The $$$m$$$ files that are currently in the Stage are numbered from $$$1$$$ to $$$m$$$ and have names $$$a_1$$$, $$$a_2$$$, ..., $$$a_m$$$.

After thinking, Yaman wants to keep only $$$k$$$ files within the Stage and the rest within Workspace. The $$$k$$$ files that he wants to keep in the Stage are numbered from $$$1$$$ to $$$k$$$ and have names $$$b_1$$$, $$$b_2$$$, ..., $$$b_k$$$.

Yaman can perform the following operations any number of times (possibly zero):

  • Move a single file from Workspace into the Stage.
  • Move all files from Workspace into the Stage.
  • Move a single file from Stage into the Workspace.
  • Move all files from the Stage into the Workspace.

Help Yaman to determine the minimum number of operations he has to make to place just the $$$k$$$ files $$$b_1$$$, $$$b_2$$$, ..., $$$b_k$$$ in the Stage.

Input

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

The first line of each test case contains three integers $$$n, m, k$$$ $$$( 1 \le n \le 100 )$$$ $$$( 0 \le m, k \le n )$$$ — the number of files in the project, the number of files that are currently in the Stage, the number of files that have to be in the Stage at the end, respectively.

The second line contains $$$n$$$ strings $$$s_1, s_2, .., s_n$$$ $$$( 1 \le |s_i| \le 100 )$$$ — the names of the files (consists of lowercase Latin letters).

The third line contains $$$m$$$ strings $$$a_1, a_2, .., a_m$$$ $$$( 1 \le |a_i| \le 100 )$$$ — the files that are currently in the Stage.

The fourth line contains $$$k$$$ strings $$$b_1, b_2, .., b_k$$$ $$$( 1 \le |b_i| \le 100 )$$$ — the files that have to be in the Stage at the end.

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

It is guaranteed that the file names are unique.

Output

Print the minimum number of operations Yaman has to make to place just the $$$k$$$ files $$$b_1$$$, $$$b_2$$$, ..., $$$b_k$$$ in the Stage.

Example
Input
2
3 1 2
implementation greedy dp
dp
greedy implementation
4 3 2
geo trees math bs
geo trees math
math bs
Output
2
3

L. Hosen and The Magical Tree!
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

In the famous $$$\textit{Uncling}$$$ city, there is a small school called the $$$\textit{Uncling}$$$ school. Hosen is a student in that school and he loves all the subjects except one and only subject... Yes, its Trees.

Eyad and Jaber are such bad bullies; they keep bullying Hosen and give him hard tree problems. $$$\textit{Stop it! I hate trees!}$$$ Hosen said. Hosen wants to take revenge on them and show them how good he can become at Trees! He decided to take the risk and... No, he won't study Trees. He will go to the magical forest to get the power of Trees from the magical grand tree.

After climbing so many trees, he finally reached the magical tree. Unfortunately, the magical grand tree will not give him the power so easily. In order to get the power of Trees, you must solve this problem! the magical grand tree said. As expected, its a tree problem :( Hosen needs help solving the problem; please help him!!

The magical grand tree will give Hosen $$$Q$$$ queries and a tree consisting of $$$N$$$ vertices and weighted edges. The distance between two vertices $$$u$$$ and $$$v$$$ in the given tree is the sum of weights of edges on the simple path between $$$u$$$ and $$$v$$$. Hosen should respond to the queries and maintain the given tree. The queries are of two types as described in the following:

  • $$$1$$$ $$$i$$$ $$$x$$$ : change the weight of the $$$i$$$-th edge to $$$x$$$.
  • $$$2$$$ $$$u$$$ $$$v$$$ : print the following sum: $$$$$$\sum_{x = 1}^N dist_x(u, v)$$$$$$
Where $$$dist_x(u, v)$$$ is the distance from vertex $$$x$$$ to the closest vertex $$$c$$$ to it, where $$$c$$$ belongs to the simple path between vertices $$$u$$$ and $$$v$$$.
Input

The first line contains two positive integers $$$N$$$, $$$Q$$$, ($$$1 \le N, Q \le 10^5$$$), the number of vertices of the given tree, and the number of queries.

The following $$$N - 1$$$ lines contain three positive integers: $$$u$$$, $$$v$$$, $$$w$$$, ($$$1 \le u, v \le N$$$), ($$$1 \le w \le 10^8$$$), describing an edge between $$$u$$$ and $$$v$$$ having weight $$$w$$$.

The following $$$Q$$$ lines describe the queries in the form mentioned above, ($$$1 \le i \le N - 1$$$), ($$$1 \le u, v \le N$$$), ($$$1 \le x \le 10^8$$$).

Output

For each query of the second type, print the answer to that query on a separate line.

Examples
Input
3 3
1 2 5
2 3 5
1 1 10
2 1 2
2 1 3
Output
5
0
Input
7 5
1 2 1
1 3 2
2 4 1
2 5 3
3 6 2
1 7 3
2 1 7
2 1 6
1 2 1
2 1 7
2 1 6
Output
13
10
11
10