The 2025 Homs Collegiate programming contest
A. The Beauty Of Homs
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Homs boasts many wonderful things: a rich history, beautiful places, and a moderate climate. What truly makes Homs special, however, are its people. They are joyful and full of life.

The judges love the people of Homs' sense of humor. So tell the judges a funny joke and make them happy, just as they'll make you happy with accepted answers.

Any non-empty string with size less than 1000 will be accepted

Any non-empty string with size less than 1000 will be accepted

Any non-empty string with size less than 1000 will be accepted

Input

A single string "tell us a joke"

Output

Any non-empty joke with size less than 1000

Example
Input
tell us a joke
Output
Mara gebna gat tekarkar gebna qaletlha Kiri Kiri

B. Colored Tree
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given an undirected tree on $$$n$$$ vertices, numbered from $$$1$$$ to $$$n$$$. Each vertex $$$v$$$ has an initial color $$$a_v$$$. You perform a uniformly random permutation of the colors $$$\{a_1, a_2, \dots, a_n\}$$$ over the $$$n$$$ vertices (all $$$n!$$$ permutations are considered different from each other).

After shuffling, define $$${ D = max_{\substack{u, \space v \space \in \{1, \space\space 2, \space\space \dots, \space\space \large{n}\} \\ a_u \neq a_v}} \mathrm{dist}(u,v). }$$$

where $$$\mathrm{dist}(u,v)$$$ is the number of edges on the unique simple path between $$$u$$$ and $$$v$$$. In other words, $$$D$$$ is the maximum distance between any two vertices that end up with different colors. If all the vertices are of the same color then $$$D$$$ is equal to $$$0$$$.

Since $$$\mathbb{E}[D]$$$ is a rational number $$$\frac{P}{Q}$$$ (with $$$Q$$$ coprime to $$$10^9 + 7$$$), output the value of $$$P \cdot Q^{-1} \bmod 10^9 + 7$$$, where $$$Q^{-1}$$$ denotes the modular inverse of $$$Q$$$ modulo $$$10^9 + 7$$$.

Input

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

Each test case is described by:

  • A line with an integer $$$n$$$ ($$$1 \le n \le 5\times 10^5$$$) — the number of vertices.
  • $$$n-1$$$ lines, each with two integers $$$u,v$$$ ($$$1 \le u,v \le n$$$) — denoting an edge of the tree.
  • A line with $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ $$$(1 \le a_i \le n)$$$ — the colors of the vertices (arbitrary integers; equal integers denote equal colors).

It is guaranteed that the sum of $$$n$$$ overall testcases does not exceed $$$5\times 10^5$$$.

Output

For each test case, print a single integer — the expected value of $$$D$$$ after a uniformly random shuffle of the colors, taken modulo $$$10^9+7$$$.

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

C. USD vs Liras
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Omar borrowed some money from his loyal and rich friend Rajaei. After successful trading, Omar now has $$$m$$$ dollars and an infinite amount of Liras. He wants to repay his debt to Rajaei over $$$n$$$ days.

You are given two arrays:

  • Array $$$a$$$ of size $$$n$$$, where $$$a_i$$$ represents the amount of dollars Rajaei demands from Omar on day $$$i$$$.
  • Array $$$b$$$ of size $$$n$$$, where $$$b_i$$$ represents the exchange rate of 1 dollar to Liras on day $$$i$$$.
Then Omar has two ways to repay the money on day $$$i$$$, let $$$c_i$$$ be the amount of liras Omar pays on day $$$i$$$.
  1. Pay $$$a_i$$$ dollars directly. There $$$c_i = 0$$$.
  2. Pay $$$x$$$ dollars $$$(0 \le x \le a_i)$$$, and cover the remaining $$$(a_i - x)$$$ dollars in liras at the exchange rate $$$b_i$$$.This means he will pay $$$c_i = (a_i - x) \times b_i$$$ liras on day $$$i$$$.

Find the minimum value $$$y$$$ such that $$$max(c_1,\space c_2, \dots,\space c_n) \le y$$$ and Omar can repay his debt using his dollars and liras.

Input

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

The first line of each test case contains two positive integers $$$n$$$ and $$$m$$$ $$$(1 \le n \le 3 \times 10^5)$$$ $$$(1 \le m \le 10^9)$$$, the number of days and the amount of dollars Omar has.

The second line of each test case contains $$$n$$$ positive integers $$${a_1, \space a_2, \dots, \space a_N}$$$ $$$(1 \le a_i \le 10^9)$$$.

The third line of each test case contains $$$n$$$ positive integers $$${b_1, \space b_2, \dots, \space b_N}$$$ $$$(1 \le b_i \le 10^9)$$$.

It is guaranteed that the sum of $$$n$$$ overall test cases doesn't exceed $$$3 \times 10^5$$$.

Output

For each test case output the minimum value $$$y$$$ such that $$$max(c_1,\space c_2, \dots,\space c_N) \le y$$$ and Omar can repay his debt using his dollars and liras.

Example
Input
1
6 23
1 8 2 2 5 10
7 3 8 2 2 3
Output
4

D. Least Uncommon Divisor
time limit per test
2 s
memory limit per test
256 megabytes
input
standard input
output
standard output

For two positive integers $$$x$$$ and $$$y$$$, define $$$lud(x,y)$$$ as the smallest positive integer $$$z$$$ that divides $$$x$$$ and doesn't divide $$$y$$$. If there is no such element, then $$$lud(x,y) = -1$$$.

For example:

$$$lud(6,4) = 3$$$

$$$lud(8,10) = 4$$$

$$$lud(10,20) = -1$$$

Given an array $$$a$$$ of size $$$n$$$ and an integer $$$x$$$, for each $$$i$$$ $$$(1 \le i \le n)$$$, find $$$lud(x,a_i)$$$.

Input

The first line contains two integers $$$n$$$ and $$$x$$$ $$$(1 \le n \le 10^6)$$$ $$$(1 \le x \le 10^{12})$$$, the length of the array $$$a$$$ and the integer $$$x$$$ respectively.

The second line contains $$$n$$$ integers $$$(1 \le a_i \le 10^{12})$$$, the elements of the array $$$a$$$.

Output

Print $$$n$$$ integers, the $$$i_{ith}$$$ of which is $$$lud(x,a_i)$$$.

Example
Input
5 30
6 10 15 35 60
Output
5
3
2
2
-1

E. a less than b
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given two strings $$$a$$$ and $$$b$$$, each of length $$$n$$$.

You can make this operation at most once:

Choose two integers $$$l$$$ and $$$r$$$ such that $$$(1 \le l \le r \le n)$$$ and reverse the substring from $$$l$$$ to $$$r$$$ of the string $$$a$$$.

Your task is to tell whether it is possible to make string $$$a$$$ lexicographically smaller than string $$$b$$$.

Input

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

The first line of each test case contains a single integer $$$n$$$ $$$(1 \le n \le 10^5)$$$, the length of strings $$$a$$$ and $$$b$$$.

The second line of each test case contains the string $$$a$$$ of length $$$n$$$.

The third line of each test case contains the string $$$b$$$ of length $$$n$$$.

Strings $$$a$$$ and $$$b$$$ contain only lowercase Latin letters.

It is guaranteed that the sum of $$$n$$$ overall test cases doesn't exceed $$$10^5$$$.

Output

For each test case, print $$$\bf{Yes}$$$ if you can make string $$$a$$$ lexicographically smaller than string $$$b$$$ using at most one operation; otherwise, print $$$\bf{No}$$$.You may print each character in either case, for example $$$\bf{YES}$$$ and $$$\bf{yEs}$$$ will also be accepted.

Example
Input
6
2
za
za
3
abb
abb
4
abza
aaza
3
bad
abd
3
bba
abd
6
cbadca
abcdcb
Output
Yes
No
No
No
Yes
Yes

F. Split
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of $$$n$$$ non-negative integers.

You need to split its elements into 2 non-empty sets $$$s_1$$$ and $$$s_2$$$, such that each element belongs to exactly one set. The value of the split is defined as the value of the following formula:

$$$$$${|and(s_1) - and(s_2)|}$$$$$$

where $$$and(s_1)$$$, $$$and(s_2)$$$ are the bitwise AND of the elements of the first and the second set in order, and $$$|x|$$$ is the absolute value of $$$x$$$.

You need to output the maximum value of a split.

Input

The first line 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$$$ $$$(2 \le n \le 10^5)$$$ — the length of array $$$a$$$.

The following line contains $$$n$$$ non-negative integers $$$(a_1, \space a_2, \space ..a_n)$$$ $$$(1 \le a_i \le 10^9)$$$ — the elements of the array.

It is guaranteed that the sum of $$$n$$$ overall testcases does not exceed $$$10^5$$$.

Output

For each testcase you need to output the maximum value of a split as described in the problem statement.

Example
Input
1
10
7 6 2 1 8 2 8 1 1 7
Output
8

G. Mexy Permutation
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

For a permutation $$$p$$$ of size $$$n$$$, define the array $$$a$$$ of size $$$n - 1$$$ as the difference array,in other words $$$(a_i = p_i - p_{i-1})$$$ for each $$$(1 \lt i \lt = n)$$$.

A permutation $$$p$$$ is $$$\it{Mexy}$$$ if the $$$mex$$$ of the difference array $$$a$$$ is greater than or equal to $$$\lfloor \frac{2n}{3} \rfloor$$$.

The $$$mex$$$ of an array is the smallest $$$\bf{positive}$$$ integer $$$x$$$ that does not exist in the array.

For example: if we have the permutation $$$p = (1,3,2)$$$, then the difference array $$$a = (2,-1)$$$ and the $$$mex$$$ of array $$$a$$$ is 1.

Given an integer $$$n$$$, find any $$$\it{Mexy}$$$ permutation $$$p$$$ of size $$$n$$$.

Note that you don't have to find the permutation with the maximum $$$mex$$$ value of array $$$a$$$, just find any $$$\it{Mexy}$$$ permutation.

Input

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

Each test case contains a single line with a single positive integer $$$n$$$ $$$(1 \le n \le 10^5)$$$, the size of the permutations $$$p$$$.

It is guaranteed there is at least one $$$\it{Mexy}$$$ permutation of size $$$n$$$.

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

Output

For each test case print any $$$\it{Mexy}$$$ permutation of size $$$n$$$.

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

H. Median Gcd
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a whiteboard with integers from $$$l$$$ to $$$r$$$ written on it, inclusive. Initially, the whiteboard contains the set of integers $$$\{l, l+1, \dots, r\}$$$. You will repeatedly perform the following two operations until the whiteboard is empty:

  1. Add the greatest common divisor (GCD) of all numbers currently on the whiteboard to your total score.
  2. Remove the median element from the whiteboard. The median of a set of $$$n$$$ elements is defined as the element at index $$$\lfloor \frac{n+1}{2} \rfloor$$$ when the elements are sorted in non-decreasing order. For example, if the elements are $$$\{2, 5, 1, 8, 3\}$$$, sorted they are $$$\{1, 2, 3, 5, 8\}$$$. Here $$$n=5$$$, $$$\lfloor \frac{5+1}{2} \rfloor = 3$$$. The element at index 3 (1-indexed) is 3, so the median is 3.

Your task is to calculate the final total score after the whiteboard becomes empty.

Input

The first line contains an integer $$$T$$$ ($$$1 \le t \le 10^5$$$), the number of testcases. Each of the following $$$t$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le 2 \times 10^9$$$).

Output

For each testcase, print a single integer representing the final total score.

Example
Input
2
1 3
3 5
Output
5
7

I. W/S TREE
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree with $$$n$$$ nodes. Each node $$$i$$$ (where $$$1 \le i \le n$$$) has a treasure with value $$$a_i$$$. The edges connecting the nodes are of two types: strong or weak.

You start exploring this tree from node 1. You want to find a walk (a sequence of connected nodes) starting at node 1 that maximizes the total value of treasures collected. The treasure at a node is collected the first time you visit that node. Subsequent visits to the same node do not yield any more treasure value.

The rules for traversing the edges depend on their type:

  • A strong edge can be traversed any number of times, in either direction.
  • A weak edge can be traversed at most once in total during your entire walk. For instance, if there is a weak edge between nodes $$$u$$$ and $$$v$$$, you can traverse it once from $$$u$$$ to $$$v$$$, or once from $$$v$$$ to $$$u$$$. After using it once in either direction, you cannot use this specific weak edge again.

Your walk can finish at any node in the tree. Determine the maximum possible sum of treasure values you can collect.

NOTE: When you step into the node, you can't skip the treasure you must collect it.

Input

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

Each test case begins with a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of nodes in the tree.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — the value of the treasure at each node.

The next $$$n-1$$$ lines describe the edges. Each line contains three integers $$$u, v, s$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$, $$$s \in \{0, 1\}$$$), representing an edge between node $$$u$$$ and node $$$v$$$. If $$$s=0$$$, the edge is weak. If $$$s=1$$$, the edge is strong.

It is guaranteed that the given graph is a tree. 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 a single line containing one integer — the maximum total value of treasures that can be collected starting from node 1.

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

J. Arranged Marriage
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

In Nlogonia city there are $$$n$$$ families,the $$$i_{ith}$$$ family has $$$b_i$$$ boys and $$$g_i$$$ girls.

For two integers $$$l$$$ and $$$r$$$ $$$(1 \le l \le r \le n)$$$ when we consider families in the range $$$[l,r]$$$, if it is possible to arrange all the boys and girls whose families are in the given range in couples, then the range $$$[l,r]$$$ is good.

Note that each boy in the given range can marry any girl from the given range,but he can't marry a girl from his family.

Your task is to count the number of good ranges.

Input

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

The first line of each test case contains an integer $$$n$$$ $$$(1 \le n \le 3 \times 10^5)$$$, the number of families.

The second line of each test case contains $$$n$$$ integers $$$b_i$$$ $$$(1 \le b_i \le 10^9)$$$, the number of boys in each family.

The third line of each test case contains $$$n$$$ integers $$$g_i$$$ $$$(1 \le g_i \le 10^9)$$$, the number of girls in each family.

It is guaranteed that the sum of $$$n$$$ overall test cases doesn't exceed $$$3 \times 10^5$$$.

Output

For each query in each test case print the number of good ranges.

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

K. Cookies
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ kids standing in a line, indexed from $$$1$$$ to $$$n$$$. Each kid $$$i$$$ has a rating $$$r_i$$$. You need to distribute cookies to these kids such that the following conditions are met:

  1. Each kid must receive at least one cookie.
  2. If kid $$$i$$$'s rating is strictly greater than kid $$$i-1$$$'s rating (i.e., $$$r_i \gt r_{i-1}$$$), then kid $$$i$$$ must receive strictly more cookies than kid $$$i-1$$$.
Your task is to find the minimum total number of cookies required to satisfy these conditions.
Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$), representing the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$), representing the number of kids.

The second line contains $$$n$$$ space-separated integers $$$r_1, r_2, \ldots, r_n$$$ ($$$1 \le r_i \le 1000$$$), representing the ratings of the kids.

Output

For each test case, output a single integer: the minimum total number of cookies required to satisfy all conditions.

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

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

Given an array $$$a$$$ of size n. We call a set of indices $$$b_1, b_2, b_3, ..., b_m$$$ good if it satisfies $$$$$$b_1+1 \lt b_2, \space b_2+1 \lt b_3, \space b_3+1 \lt b_4, \space ...., \space b_{m-1}+1 \lt b_m $$$$$$ and so on. And the score of this good set is: $$$$$$max(a_{b_1}, \space a_{b_2}, \space a_{b_3}, \space ..., \space a_{b_m})$$$$$$ For each integer $$$ i \space (1 \le i \le n)$$$ output the minimum score of a good set of size $$$i$$$ or $$$-1$$$ if there are no good sets.

Input

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

Each test case contains two lines: In the first line, there is a single integer $$$n$$$ $$$(1 \le n \le 10^6)$$$, the size of the array. In the second line, there are $$$n$$$ integers $$$a_1, a_2, a_3, ..., a_n (1 \le a_i \le 10^9)$$$, the elements of the array. It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^6$$$.

Output

For each test case, output n integers, the minimum score of a good set of size $$$i (1 \le i \le n)$$$ or $$$-1$$$ if there are no good sets.

Example
Input
5
1
5
2
4 3
6
2 3 7 2 1 5
8
1 2 1 2 1 2 1 2
5
100000 1000000 10000000 100000000 1000000000
Output
5 
3 -1 
1 2 5 -1 -1 -1 
1 1 1 1 -1 -1 -1 -1 
100000 10000000 1000000000 -1 -1

M. Random Spanning Tree
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

We say that the diameter of a tree is any longest simple path in that tree, and we measure the length of a path by the number of edges it contains.

You are given a positive integer $$$n$$$. Consider the undirected complete graph on vertices $$$\{1,2,\ldots,n\}$$$. A spanning tree $$$T$$$ is chosen uniformly at random among all spanning trees satisfying that the simple path between vertices $$$1$$$ and $$$n$$$ is a diameter of $$$T$$$. Equivalently, if $$$d(u,v)$$$ denotes the distance (number of edges) between $$$u$$$ and $$$v$$$ in $$$T$$$, then $$$$$$ d(1,n) \;=\; \max_{1 \le x \lt y \le n} d(x,y). $$$$$$

Let $$$$$$ D \;=\; d(1,n) $$$$$$ in the chosen tree. We have $$$$$$ \mathbb{E}[D] \;=\;\frac{P}{Q}, $$$$$$ a rational number, where $$$\mathbb{E}[D]$$$ denotes the expected (average) value of the random variable $$$D$$$ taken over all valid spanning trees $$$T$$$ chosen under the given condition.

You are also given an integer $$$m$$$. Since $$$\mathbb{E}[D]$$$ is a rational number $$$\frac{P}{Q}$$$ (with $$$Q$$$ coprime to $$$m$$$), output the value of $$$P \cdot Q^{-1} \bmod m$$$, where $$$Q^{-1}$$$ denotes the modular inverse of $$$Q$$$ modulo $$$m$$$.

Input

The first line contains two integers:

  • $$$t$$$ ($$$1 \le t \le 500$$$) — the number of testcases.
  • $$$m$$$ ($$$10^8 \le m \le 10^9$$$, $$$m$$$ is prime).
Each of the next $$$t$$$ lines contains a single integer $$${n \space\space (1 \le n \le 500)}$$$ — denoting the number of nodes in the graph for that testcase.
Output

For each testcase, output in the answer to the problem modulo $$$m$$$ in a separate line.

Example
Input
8 711787309
1
2
3
4
5
6
7
8
Output
0
1
2
355893657
305051707
211612447
511987367
529573609