ASU Coding Cup 10
A. The Giraffe and the Beautiful number
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

For a positive integer $$$n$$$, define $$$f(n)$$$ to be the number of non-empty substrings of $$$n$$$ that are divisible by $$$3$$$. For example, the string $$$2573$$$ has $$$10$$$ non-empty substrings, three of which represent numbers that are divisible by $$$3$$$, namely $$$3$$$, $$$57$$$, and $$$573$$$. So $$$f(2573) = 3$$$.

The Giraffe thinks that if $$$f(n)$$$ is divisible by $$$3$$$, then we say that $$$n$$$ is a beautiful number.

Define $$$F(d)$$$ to be the number of $$$d$$$ digit numbers that are beautiful.

Find $$$F(d)$$$. Give your answer modulo $$$1\,000\,000\,007$$$.

Input

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

Each test case consists of a single integer $$$d$$$ ($$$1 \le d \le 10^5$$$).

The sum of $$$d$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output

Print the answer.

Example
Input
2
2
6
Output
30
290898

B. The Great Zebra Quest at ASZoo (Easy)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the easy version of the problem; the only difference between the easy and hard versions is $$$k = 1$$$.

Deep in the heart of the city lies ASZoo, a sprawling wildlife park known for its winding pathways, lush habitats, and the majestic herds of zebras in its savanna exhibit. As the annual Zebra Spotlight Festival approaches, the ASZoo team needs to map out the shortest route from every park corner to the nearest zebra enclosure, so visitors can dash off to see these striped wonders without getting lost.

In this problem, model the park as an undirected, unweighted, simple graph:

  • Nodes ($$$1$$$ through $$$N$$$): distinct locations in ASZoo—exhibit areas, rest stops, food kiosks, or pathway junctions.
  • Edges: bidirectional pathways connecting two locations; moving along an edge is one "step".

Among these locations, exactly $$$K$$$ contain zebra enclosures. For each location $$$i$$$, compute the minimum number of steps needed to reach any zebra enclosure. If $$$i$$$ itself has a zebra enclosure, its distance is $$$0$$$. If $$$i$$$ cannot reach any zebra enclosure, output $$$-1$$$.

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 3 integers $$$n$$$, $$$m$$$, $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$), ($$$1 \le m \le min(2 \cdot 10^5, \frac{n \cdot (n - 1)}{2})$$$), ($$$k = 1$$$).

The next $$$m$$$ lines contains two integers, $$$u_i$$$, $$$v_i$$$ ($$$1 \le u, v \le n, u \neq v$$$), denots the edges. The $$${m + 2}^nd$$$ line contains $$$k$$$ integers ($$$ 1 \le a_i \le n$$$) denots the locations that contain zebra enclosures.

The sum of $$$n$$$, and $$$m$$$ doesn't exceed $$$2 \cdot 10^5$$$ over all test cases.

Output

For each test case, print a single line containing the following:

For each location from $$$1$$$ through $$$n$$$, print the minimum number of pathway steps required to reach any zebra enclosure.

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

C. The Great Zebra Quest at ASZoo (Hard)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the hard version of the problem; the only difference between the easy and hard versions is $$$k$$$ ($$$1 \le k \le n$$$)

Deep in the heart of the city lies ASZoo, a sprawling wildlife park known for its winding pathways, lush habitats, and the majestic herds of zebras in its savanna exhibit. As the annual Zebra Spotlight Festival approaches, the ASZoo team needs to map out the shortest route from every park corner to the nearest zebra enclosure, so visitors can dash off to see these striped wonders without getting lost.

In this problem, model the park as an undirected, unweighted, simple graph:

  • Nodes ($$$1$$$ through $$$N$$$): distinct locations in ASZoo—exhibit areas, rest stops, food kiosks, or pathway junctions.
  • Edges: bidirectional pathways connecting two locations; moving along an edge is one "step".

Among these locations, exactly $$$K$$$ contain zebra enclosures. For each location $$$i$$$, compute the minimum number of steps needed to reach any zebra enclosure. If $$$i$$$ itself has a zebra enclosure, its distance is $$$0$$$. If $$$i$$$ cannot reach any zebra enclosure, output $$$-1$$$.

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 3 integers $$$n$$$, $$$m$$$, $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$), ($$$1 \le m \le min(2 \cdot 10^5, \frac{n \cdot (n - 1)}{2})$$$), ($$$1 \le k \le n$$$).

The next $$$m$$$ lines contains two integers, $$$u_i$$$, $$$v_i$$$ ($$$1 \le u, v \le n, u \neq v$$$), denots the edges. The $$${m + 2}^nd$$$ line contains $$$k$$$ integers ($$$ 1 \le a_i \le n$$$) denots the locations that contain zebra enclosures.

The sum of $$$n$$$, and $$$m$$$ doesn't exceed $$$2 \cdot 10^5$$$ over all test cases.

Output

For each test case, print a single line containing the following:

For each location from $$$1$$$ through $$$n$$$, print the minimum number of pathway steps required to reach any zebra enclosure.

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

D. ASZoo Animals
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are a lot of animals in ASZoo, and each kind of animal has a family.

There is $$$n$$$ kind of animals, each kind has $$$a_i$$$ family member, count how many animals in the Zoo.

Input

The first line of input consists of a single integer $$$n$$$ ($$$1 \le n \le 100$$$).

The second line of input consists of $$$n$$$ integers $$$a_1, a_2, ... a_n$$$ ($$$1 \le a_i \le 100$$$).

Output

Print the answer.

Examples
Input
4
3 1 2 5
Output
11
Input
1
6
Output
6
Input
3
1 1 1
Output
3

E. Kilani The Tiger (Easy)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the easy version of the problem; the difference between the easy and hard versions is that the hard version requires queries.

Kilani the tiger is the greatest competitive programmer not only in ASZoo but also in the world. And he's well known as Az3ar, but at home they call him "keko", and he doesn't like this name.

He found a string with $$$n$$$ characters, and he wants to find the number of subsequences in the string that contain the word "keko" to determine whether people already know his name.

Given a string $$$s$$$ that consists of $$$n$$$ lowercase Latin letters, find how many subsequences are equal to the word "keko"; the answer will be very large. So, print it modulo $$$1\,000\,000\,007$$$.

A subsequence of a string is a string that can be obtained by removing several (possibly zero) characters from the original string.

For example, consider the string "abac", "aa", "ac", "ba" are subsequences of it, but "ca" is not.

Input

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

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

The second line of each test case consists of a string $$$s$$$ ($$$|s| = n$$$)

The sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output

For each testcase, print the answer modulo $$$1\,000\,000\,007$$$..

Example
Input
2
6
kkkeko
6
kkekoo
Output
3
4

F. Kilani The Tiger (Hard)
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the hard version of the problem; the difference between the easy and hard versions is that the hard version requires queries.

Kilani the tiger is the greatest competitive programmer not only in ASZoo but also in the world. And he's well known as Az3ar, but at home they call him "keko", and he doesn't like this name.

He found a string with $$$n$$$ characters, and he wants to find the number of subsequences in the string that contain the word "keko" to determine whether people already know his name.

Given a string $$$s$$$ that consists of $$$n$$$ lowercase Latin letters. And you'll be given $$$q$$$ queries, on each query, find how many subsequences are equal to the word "keko" in the substring in range $$$l$$$, $$$r$$$ ($$$1 \le l \le r \le |s|$$$).

More formally, find the number of subsequences that equals "keko" in the substring $$$s_l, s_{l+1}, s_{l+2}, ..., s_{r-1}, s_3$$$.

The answer will be very large. So, print it modulo $$$1\,000\,000\,007$$$.

A subsequence of a string is a string that can be obtained by removing several (possibly zero) characters from the original string.

For example, consider the string "abac", "aa", "ac", "ba" are subsequences of it, but "ca" is not.

Input

The input contains only one test case.

The first line consists of a single integer $$$n$$$, $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$).

The second line consists of a string $$$s$$$ ($$$|s| = n$$$)

The next $$$q$$$ lines consists of two integer $$$l_i$$$, $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$).

Output

For each query, print the answer modulo $$$1\,000\,000\,007$$$..

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

G. Cheetahs Hunting Deers (Easy)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the wildlife outside ASZoo, there are living $$$n$$$ cheetahs and $$$m$$$ deers, and as we all know that the deers are the cheetahs' favorite food.

Each cheetah has power equal to $$$a_i$$$ ($$$1 \le i \le n$$$), and each deer has power equal to $$$b_i$$$ ($$$1 \le i \le m$$$).

The cheetah can eat a deer only if the deer's power is strictly less than the cheetah's power.

Each cheetah wants to eat one deer, and each deer can be eaten once. Can you know whether all the cheetahs will have their dinner or not?

Input

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

The first line of each test case consists of two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$).

The second line of each test case consists of $$$n$$$ integers $$$a_1, a_2, ..., a_n$$$ ($$$1 \le a_i \le 10^9$$$).

The third line of each test case consists of $$$m$$$ integers $$$b_1, b_2, ..., b_n$$$ ($$$1 \le b_i \le 10^9$$$).

The sum of $$$n$$$ and $$$m$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print "YES" if all cheetahs can eat deers, "No" otherwise (case insensitive).

Example
Input
2
2 3
3 2
4 2 1
4 6
1 1 1 1
1 1 1 1 1 1
Output
Yes
No

H. Cheetahs Hunting Deers (Hard)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the wildlife outside ASZoo, there are living $$$n$$$ cheetahs and $$$m$$$ deers, and as we all know that the deers are the cheetahs' favorite food.

Each cheetah has power equal to $$$a_i$$$ ($$$1 \le i \le n$$$), and each deer has power equal to $$$b_i$$$ ($$$1 \le i \le m$$$).

The cheetah can eat a deer only if the deer's power is strictly less than the cheetah's power.

Each cheetah wants to eat one deer, and each deer can be eaten once. Can you know whether all the cheetahs will have their dinner or not? And if they can, what is the index of the deer that each cheetah will eat?

Input

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

The first line of each test case consists of two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$).

The second line of each test case consists of $$$n$$$ integers $$$a_1, a_2, ..., a_n$$$ ($$$1 \le a_i \le 10^9$$$).

The third line of each test case consists of $$$m$$$ integers $$$b_1, b_2, ..., b_n$$$ ($$$1 \le b_i \le 10^9$$$).

The sum of $$$n$$$ and $$$m$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print "YES" if all cheetahs can eat deers, "No" otherwise (case insensitive). If the answer was "YES", print $$$n$$$ distinct integers $$$index_i$$$ denoting the $$$index$$$ of the deer the $$$i^{th}$$$ cheetah will eat. If there are multiple answers, print any of them.

Example
Input
2
2 3
3 2
4 2 1
4 6
1 1 1 1
1 1 1 1 1 1
Output
Yes
2 3 
No

I. The Youngest in ASZoo
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are two monkeys in ASZoo, the first one's age is $$$n$$$ and the second one is $$$m$$$, print the age of the younger monkey.

Input

The input consists of two integers $$$n$$$, and $$$m$$$ ($$$ 1 \le n, m \le 100$$$).

Output

Print the age of the younger monkey.

Examples
Input
3 5
Output
3
Input
7 1
Output
1

J. Zmeh The ASZoo Keeper
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Zmeh is a zookeeper at ASZoo. He knows the number of animals in each family, so he wants to challenge you.

Given an array of $$$n$$$ strings $$$s$$$ denoting the kind of each animal in the zoo, and $$$q$$$ queries.

On each query, you'll be given a string $$$t$$$ and you must find the number of animals that are from that family.

Input

The first line of input consists of two integers $$$n$$$, $$$q$$$ ($$$ 1 \le n, q \le 6 \cdot 10^4$$$).

The second line of input consists of $$$n$$$ strings $$$s_1, s_2, ..., s_n$$$ ($$$1 \le |s_i| \le 10$$$).

The next q lines consist of $$$t_i$$$ ($$$1 \le |t_i| \le 10$$$).

Output

For each test case, print the number of animals that are from family $$$t_i$$$.

Example
Input
4 4
dog cat dog dog
dog
cat
dog
lion
Output
3
1
3
0

K. The Cage in ASZoo
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There is A huge cage in ASZoo that can contain up to $$$k$$$ animals.

There are $$$n$$$ families of animals, each of which has an infinite family members, and each kind of animal weighs $$$a_i$$$ ($$$1 \le i \le n$$$).

The zookeeper decided to put exactly $$$k$$$ animals in the cage, regardless of the kind or the weight. The zookeeper can put more than one animal of the same family in the cage, and can also discard an entire family and not putting them in the cage.

Find all possible total weights of animals that the zookeeper can put in the cage.

Input

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n, k \le 1000$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, ..., a_n$$$ ($$$1 \le a_i \le 1000$$$).

Output

Print the only line with all the possible total weights of stolen products, separated by a space. The numbers should be printed in ascending order.

Examples
Input
3 2
1 2 3
Output
2 3 4 5 6
Input
5 5
1 1 1 1 1
Output
5
Input
3 3
3 5 11
Output
9 11 13 15 17 19 21 25 27 33

L. The Elephant and the Array
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In ASZoo, the elephant wants to solve an interesting problem.

Given an array $$$a$$$ of length $$$n$$$ and array $$$b$$$ of length $$$m$$$, ($$$b$$$ values are unique).

The elephant wants to do the following operations until no element in $$$a$$$ exists in $$$b$$$.

  • In the first operation, the elephant deletes the first element of the array.
  • In the second operation, the elephant deletes the last element of the array ($$$a_n$$$).
  • In the third operation, the elephant deletes the second element of the array ($$$a_2$$$).

And he keeps doing the same operation until the condition is met or the array becomes empty.

More formally, in the operation $$$i$$$ where ($$$i \equiv 1 (mod 2)$$$), the elephant deletes the element at the beginning of the array.

And in operation ($$$i \equiv 0 (mod 2)$$$), the elephant deletes the element at the end of the array.

Calculate the minimum number of operations to meet the condition.

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 consists of two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$).

The second line of each test case consists of $$$n$$$ integers $$$a_1, a_2, ..., a_n$$$ ($$$1 \le a_i \le 10^6$$$).

The third line of each test case consists of $$$m$$$ integers $$$b_1, b_2, ..., b_n$$$ ($$$1 \le b_i \le 10^6$$$).

The sum of $$$n$$$ and $$$m$$$ doesn't exceed $$$2 \cdot 10^5$$$ over all test cases.

Output

For each test case, print the answer.

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

M. The Smartest at ASZoo
time limit per test
15 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Corvus the Crow, ASZoo's resident genius, loves tackling number-theory puzzles.

In this problem, Corvus is given a positive integer $$$n$$$ and must count how many unordered pairs of distinct numbers between $$$1$$$ and $$$n$$$ are coprime, The number could be very large, so print it modulo $$$1 000 000 007$$$.

A pair $$$(i,j)$$$ with $$$1 \le i \lt j \le n$$$ is called coprime if $$$\gcd(i,j) = 1$$$. Compute the total number of such pairs.

Input

The only integer in the input is $$$n$$$, ($$$2 \le n \le 10^{11}$$$).

Output

Print the answer.

Examples
Input
100
Output
3044
Input
59
Output
1086
Input
1765
Output
947722