JU Cup 2026
A. [RED] Can you say Hello Hello?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Jebreel is coming to the University of Jordan to judge say Hello Hello to him

Input

no input

Output

print Hello Hello

Example
Input
no input
Output
Hello Hello

B. [Orange] Can you count the roads ?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Aziz is lost in University of Jordan and decides to set a goal: he wants to walk exactly $$$N$$$ roads before sitting down. The campus paths are structured into two types of circular routes: short routes consisting of exactly $$$2$$$ roads, and long routes consisting of exactly $$$3$$$ roads.

He wants to walk exactly $$$N$$$ roads while completing the minimum possible number of total routes. If it is impossible to walk exactly $$$N$$$ roads using only routes of $$$2$$$ and $$$3$$$, output $$$-1$$$.

Input

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

The first line and only line of each test case contains one integer $$$N$$$ ($$$1 \le N \le 10^5$$$) — denotes the the exact number of roads Aziz wants to walk.

Output

for each test case, print a single integer representing the minimum number of routes Aziz needs to walk, or -1 if it is impossible.

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

C. [Blue] Can you make it palindrome?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Abushogi loves symmetric words. He is given a string $$$s$$$ consisting of lowercase English letters, and a specific lowercase English letter $$$c$$$.

He wants to transform the string $$$s$$$ into a palindrome (a string that reads the same forwards and backwards, for example, maram and toot is palindrome, but hello is not palindrome).

To do this, he can perform the following operation as many times as he likes (possibly zero):

  • Insert the character $$$c$$$ anywhere into the string $$$s$$$. He can place it before the first character of $$$s$$$, after the last character, or between any two adjacent characters.

Given the string $$$s$$$ and the character $$$c$$$, help Abushogi determine if it is possible to turn the string into a palindrome using only this operation.

Input

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

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$) and a character $$$c$$$ (a lowercase English letter) separated by a space — denotes the length of the string and the character Abushogi is allowed to insert.

The second line of each test case contains the string $$$s$$$ of length $$$n$$$, consisting only of lowercase English letters.

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 YES if Abushogi can make the string a palindrome. Otherwise, output NO.

Example
Input
3
3 b
aba
4 b
abca
2 c
ab
Output
YES
YES
NO

D. [Green] Can you do the AND math ?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Abushogi has spent too many hours in the lab and is slowly going insane. It only makes sense how he came up with this bizarre function.Let's define $$$f(b)$$$ as the maximum possible score you can achieve from an array $$$b$$$ of size $$$m$$$ by playing the following game:

  • While there is more than $$$1$$$ element in the array, choose any two elements $$$x$$$ and $$$y$$$ and remove them;
  • Add $$$\max(x, y)$$$ to your score;
  • Insert a single element equal to $$$x \ \& \ y$$$ (the bitwise AND of $$$x$$$ and $$$y$$$) back into the array.

The game ends after exactly $$$m-1$$$ operations when only one element remains. (If $$$m=1$$$, you make $$$0$$$ operations and the score is $$$0$$$).MrMoon saw Abushogi's function and felt it was too easy for his students. So, he gave them an array $$$a$$$ of size $$$n$$$ and an assignment: calculate the sum of the scores $$$f(a_1, a_2, \dots, a_i)$$$ for all prefixes $$$i$$$ from $$$1$$$ to $$$n$$$.

In other words, you need to calculate:$$$$$$\sum_{i=1}^{n} f(a[1 \dots i])$$$$$$Help the students solve MrMoon's assignment!

Input

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

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

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^7$$$) — denotes the elements of the array.

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 a single integer — the sum of the maximum scores for all prefixes of the array $$$a$$$.

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

E. [Yellow] Can you do the OR math ?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

After his students easily solved his previous assignment involving Abushogi's bizarre function, MrMoon felt deeply humiliated.

Determined to take his revenge and finally stump his students, MrMoon has created a new version, he decided that instead of replacing the elements with "$$$x$$$ AND $$$y$$$", the game will now replace them with "$$$x$$$ OR $$$y$$$".

MrMoon is now struggling to calculate the answers himself and needs your help to verify his test cases. You are given an array $$$a$$$ of size $$$n$$$. You play a game exactly $$$n-1$$$ operations. In each operation, you do the following:

  • Choose any two elements $$$x$$$ and $$$y$$$ from the array and remove them;
  • Add $$$\max(x, y)$$$ to your score;
  • Insert a single element equal to $$$x \ \vert{} \ y$$$ (the bitwise OR of $$$x$$$ and $$$y$$$) back into the array.

The game ends after exactly $$$n-1$$$ operations when only one element remains. (If $$$n=1$$$, you make $$$0$$$ operations and your score is $$$0$$$).

Let $$$f(a)$$$ be the maximum possible score you can achieve from the array $$$a$$$. Your task is to find $$$f(a)$$$.

Input

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

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

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^7$$$) — denotes the elements of the array.

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 a single integer — the maximum possible score $$$f(a)$$$ you can achieve after $$$n-1$$$ operations.

Example
Input
3
3
3 2 4
1
10
4
1 2 4 8
Output
11
0
34
Note

In the first test case, the array is [3, 2, 4]. The optimal strategy is as follows: Choose $$$x = 4$$$ and $$$y = 3$$$. You add $$$\max(4, 3) = 4$$$ to your score. You remove $$$4$$$ and $$$3$$$, and insert $$$4 \ \vert{} \ 3 = 7$$$ back into the array. The array becomes [7, 2]. Choose $$$x = 7$$$ and $$$y = 2$$$. You add $$$\max(7, 2) = 7$$$ to your score. You remove $$$7$$$ and $$$2$$$, and insert $$$7 \ \vert{} \ 2 = 7$$$ back into the array. The array becomes [7].

The game ends because only one element remains. Your total score is $$$4 + 7 = 11$$$.

In the second test case, $$$n = 1$$$, so you perform $$$0$$$ operations and the total score is $$$0$$$.

In the third test case, the array is [1, 2, 4, 8]. First, pair $$$8$$$ and $$$4$$$. Score increases by $$$8$$$, insert $$$8 \ \vert{} \ 4 = 12$$$. Array is [1, 2, 12].Next, pair $$$12$$$ and $$$2$$$. Score increases by $$$12$$$, insert $$$12 \ \vert{} \ 2 = 14$$$. Array is [1, 14].Finally, pair $$$14$$$ and $$$1$$$. Score increases by $$$14$$$, insert $$$14 \ \vert{} \ 1 = 15$$$. Array is [15].Total score = $$$8 + 12 + 14 = 34$$$.

F. [Purple] Can you find the good number ?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Essam was observing the night sky when the Moon challenged him with a mathematical puzzle.A positive integer is called good if all of its digits are identical (for example, $$$7$$$, $$$22$$$, and $$$555$$$ are good numbers, while $$$15$$$ and $$$100$$$ are not).The Moon gives Essam a positive integer $$$n$$$.

Essam needs to check if both of the following conditions are true:

  1. $$$n$$$ is a good number;
  2. $$$n \times 1.5$$$ is an integer (has no decimal part) and is also a good number.

Help Essam write a program to answer the Moon's question!

Input

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

The only line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^{18}$$$) — denotes the number Moon wants to multiply by 1.5.

Output

For each test case, output "YES" if $$$n \times 1.5$$$ is a good number, and "NO" otherwise.

You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).

Example
Input
5
2
44
3
222
88
Output
YES
YES
NO
YES
NO

G. [White] Can You find the Area ?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Laith was walking around the University of Jordan with Aziz, they were trying to have fun, so Aziz decided to give Laith a regular polygon with $$$N$$$ vertices (an $$$N$$$-gon) has $$$n$$$ equal sides and $$$N$$$ equal angles and give Laith a side length $$$S$$$.

After that, Aziz will ask Laith $$$Q$$$ questions, in each question Aziz will give Laith $$$3$$$ vertices of the $$$n$$$-gon, Laith needs to find the area of the resulted triangle when connecting the $$$3$$$ points.

Input

The first line contains one integer $$$T$$$ ($$$1 \le T \le 10^4)$$$ –denotes the number of test cases.

The first line of each test case contains three integers $$$N$$$, $$$S$$$, and $$$Q$$$ ($$$3 \le N \le 10^9$$$, $$$1 \le S \le 1000$$$, $$$1 \le Q \le 2 \cdot 10^5$$$) — denotes the number of vertices in the polygon, the side length of the polygon, and the number of queries, respectively.

Each of the next $$$Q$$$ lines contains three integers $$$u$$$, $$$v$$$, and $$$w$$$ ($$$1 \le u, v, w \le N$$$) — denotes the indices of the vertices chosen for the query.

It is guaranteed that $$$u, v$$$, and $$$w$$$ are distinct.

Output

For each query, output the area of the triangle formed by the vertices $$$u, v$$$, and $$$w$$$.

Your answer will be considered correct if its absolute or relative error does not exceed $$$10^{-9}$$$. Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{\vert{}a - b\vert{}}{\max(1, \vert{}b\vert{})} \le 10^{-9}$$$.

Example
Input
2
3 1 1
1 2 3
6 5 2
1 3 5
1 2 4
Output
0.433012702
32.475952642
21.650635095

H. [Light Green] Can you raise the sheeps ?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

On a farm owned by Void and Abukhass near the University of Jordan, there are $$$n$$$ sheep. They want to shear as many sheep as possible using a single pair of shears.

The shears have an initial durability of $$$X$$$. Shearing the $$$i$$$-th sheep decreases the durability of the shears by $$$a_i$$$. The shears break if their durability drops below zero, meaning they can only shear a sheep if $$$a_i$$$ is less than or equal to the remaining durability.

What is the maximum number of sheep they can successfully shear?

Input

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

The first line of each test case contains two space-separated integers $$$n$$$ and $$$X$$$ $$$(1 \le n \le 10^5, 1 \le X \le 10^{14})$$$ — denotes the number of sheep and the initial durability of the shears.

The second line contains $$$n$$$ space-separated integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ $$$(1 \le a_i \le 10^9)$$$ — denotes the durability cost to shear each sheep.

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 a single integer on a new line — the maximum number of sheep Void and Abukhass can shear.

Example
Input
4
4 10
3 4 2 5
3 5
6 7 8
3 100
1 2 3
2 1000000000000
1000000000 1000000000
Output
3
0
3
2

I. [Violet] Can you save money ? (Easy version)
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 medium versions is the constraints on $$$n$$$.

Abushogi is in a clothing shop with $$$n$$$ items. The $$$i$$$-th item has a price of $$$a_i$$$ dinars and brings Abushogi a happiness worth of $$$b_i$$$.

The shop has given him an offer he can't refuse: if he buys exactly $$$2$$$ distinct items, he gets a $$$50\%$$$ discount (rounded down, for example if the prices is $$$7$$$ it becomes $$$3$$$) on the more expensive item. If both items have the exact same price, the discount is applied to one of them.

Abushogi has exactly $$$k$$$ dinars. He wants to buy exactly $$$2$$$ items to maximize his total happiness without exceeding his budget.

Help Abushogi find the maximum total happiness he can achieve, or tell him if it's impossible to afford any pair of items.

Input

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

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 1000$$$, $$$1 \le k \le 2 \cdot 10^9$$$) — denotes the number of items in the shop and the amount of dinars Abushogi has.

The next $$$n$$$ lines each contain two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le 10^9$$$) — denotes the price and happiness value of the $$$i$$$-th item.

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

Output

For each testcase, print a single integer — the maximum total happiness Abushogi can achieve. If it is impossible to buy exactly $$$2$$$ items without exceeding $$$k$$$ dinars, print -1.

Example
Input
3
3 10
4 5
8 6
10 6
2 5
10 100
10 100
4 12
6 4
10 5
12 10
20 20
Output
11
-1
14
Note

Abushogi can pick the 1st item ($$$a=4, b=5$$$) and the 2nd item ($$$a=8, b=6$$$). The 2nd item is more expensive, so its price becomes $$$8 / 2 = 4$$$. The total cost is $$$4 + 4 = 8$$$, which is $$$\le 10$$$. The total happiness is $$$5 + 6 = 11$$$

J. [Violet] Can you save money ? (Medium version)
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the medium version of the problem. The only difference between the easy and medium versions is the constraints on $$$n$$$.

Abushogi is in a clothing shop with $$$n$$$ items. The $$$i$$$-th item has a price of $$$a_i$$$ dinars and brings Abushogi a happiness worth of $$$b_i$$$.

The shop has given him an offer he can't refuse: if he buys exactly $$$2$$$ distinct items, he gets a $$$50\%$$$ discount (rounded down, for example if the prices is $$$7$$$ it becomes $$$3$$$) on the more expensive item. If both items have the exact same price, the discount is applied to one of them.

Abushogi has exactly $$$k$$$ dinars. He wants to buy exactly $$$2$$$ items to maximize his total happiness without exceeding his budget.

Help Abushogi find the maximum total happiness he can achieve, or tell him if it's impossible to afford any pair of items.

Input

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

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le k \le 2 \cdot 10^9$$$) — denotes the number of items in the shop and the amount of dinars Abushogi has.

The next $$$n$$$ lines each contain two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le 10^9$$$) — denotes the price and happiness value of the $$$i$$$-th item.

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

Output

For each testcase, print a single integer — the maximum total happiness Abushogi can achieve. If it is impossible to buy exactly $$$2$$$ items without exceeding $$$k$$$ dinars, print -1.

Example
Input
3
3 10
4 5
8 6
10 6
2 5
10 100
10 100
4 12
6 4
10 5
12 10
20 20
Output
11
-1
14

K. [Gold] Can you save money ?
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Abushogi is in a clothing shop with $$$n$$$ items. The $$$i$$$-th item has a price of $$$a_i$$$ dinars and brings Abushogi a happiness worth of $$$b_i$$$.

The shop has given him an offer he can't refuse: if he buys exactly $$$2$$$ distinct items, he gets a $$$50\%$$$ discount (rounded down) on one of them! However, the shop manager applies the discount based on a specific rule:

  1. The discount is applied to the item that brings more happiness;
  2. If both items bring the exact same amount of happiness, the shop manager is generous and applies the discount to the more expensive item to save Abushogi the most money. (If both the happiness and price are equal, the discount can apply to either).

Abushogi has exactly $$$k$$$ dinars. He wants to buy exactly $$$2$$$ items to maximize his total happiness without exceeding his budget.Help Abushogi find the maximum total happiness he can achieve, or tell him if it's impossible to afford any pair of items.

Input

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

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le 2 \cdot 10^9$$$) — denotes the number of items in the shop and the amount of dinars Abushogi has.

The next $$$n$$$ lines each contain two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le 10^9$$$) — denotes the price and happiness value of the $$$i$$$-th item.

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

Output

For each testcase, print a single integer — the maximum total happiness Abushogi can achieve. If it is impossible to buy exactly 2 items without exceeding $$$k$$$ dinars, print -1.

Example
Input
3
3 10
8 5
6 10
4 4
2 10
10 100
4 100
3 5
10 1
10 2
8 3
Output
14
200
-1

L. [Pink] Can you find the pattern ?
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Seal loves making repeating patterns with words. He has a text of length $$$N$$$ and a budget of $$$K$$$ changes. He wants to choose a short word block and repeat it back-to-back until it forms a new text of length exactly $$$N$$$.

Help Seal find the shortest possible length for his repeating block so that his new text differs from his original text by at most $$$K$$$ characters.

Input

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

The first line of each test case contains two integers $$$N$$$ and $$$K$$$ ($$$1 \le N \le 2 \cdot 10^5$$$, $$$0 \le K \le N$$$) — denotes the length of the string $$$S$$$ and the maximum number of allowed character differences.

The second line of each test case contains the string $$$S$$$ of length $$$N$$$ consisting of lowercase English letters.

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 a single integer — the minimum possible length of $$$M$$$.

Example
Input
3
6 1
abaaba
4 0
abcd
6 1
abacab
Output
3
4
2

M. [Black] Can you find a better game ?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

MrMoon loves playing video games. He has $$$n$$$ favorite games, numbered $$$1$$$ to $$$n$$$. To find out which game is the absolute best, he asked $$$k$$$ reviewers to rank them. Each reviewer provided a list ranking all $$$n$$$ games from 1st place to $$$n$$$-th place.

MrMoon says that Game $$$A$$$ is better than Game $$$B$$$ if:

  • Game $$$A$$$ is ranked ahead of Game $$$B$$$ by at least one reviewer, or;
  • There is some Game $$$C$$$ where Game $$$A$$$ is better than Game $$$C$$$, and Game $$$C$$$ is better than Game $$$B$$$.

Sometimes, the reviewers disagree so much that Game $$$A$$$ is better than Game $$$B$$$, and Game $$$B$$$ is also better than Game $$$A$$$. When this happens, MrMoon calls the pair of games $$$(A, B)$$$ a confusing pair.

MrMoon wants to analyze the reviewers' lists. He has $$$q$$$ queries. For each query, he looks at a specific reviewer's list (from $$$1$$$ to $$$k$$$) and selects a contiguous subsegment of rankings from position $$$l$$$ to position $$$r$$$. He wants to know: how many confusing pairs of games exist entirely within this subsegment?

To ensure you are answering queries online, they are encoded. You must decode them using the answer to the previous query.

Input

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

For each testcase:

The first line contains three integers $$$n$$$, $$$k$$$, and $$$q$$$ ($$$1 \le n, k, q \le 2 \cdot 10^5$$$, $$$\sum n \times k \le 2 \cdot 10^5$$$, $$$\sum q \le 2 \cdot 10^5$$$) — denotes the number of games, reviewers, and queries.

The next $$$k$$$ lines each contain $$$n$$$ distinct integers $$$a_{i,1}, a_{i,2}, \dots, a_{i,n}$$$ ($$$1 \le a_{i,j} \le n$$$) — denotes the ranking list of the $$$i$$$-th reviewer.

The next $$$q$$$ lines each contain three integers $$$id'_i, l'_i, r'_i$$$. You must decode them using the answer to the previous query (let $$$ans$$$ be the previous answer, initially $$$0$$$):

  • $$$id_i = ((id'_i + ans) \pmod k) + 1$$$;
  • $$$l_i = ((l'_i + ans) \pmod n) + 1$$$;
  • $$$r_i = ((r'_i + ans) \pmod n) + 1$$$

Ensure that you swap $$$l_i$$$ and $$$r_i$$$ if $$$l_i \gt r_i$$$.

Output

For each query, output a single integer: the number of confusing pairs in the given range.

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

In the second test case, we have 4 games and 2 reviewers, so.

Reviewer 1 ranks them: 1 2 3 4

Reviewer 2 ranks them: 2 1 4 3

From these lists, Game 1 is better than Game 2 (Reviewer 1) and Game 2 is better than Game 1 (Reviewer 2). They form a confusing pair. Similarly, Game 3 and Game 4 form another confusing pair.

Let's break down MrMoon's queries. ans starts at 0. Query 1:

The input is 0 0 1.

Decode id: ((0 + 0) Decode l: ((0 + 0) Decode r: ((1 + 0) We look at Reviewer 1's list from position 1 to 2: [1, 2].

There is exactly 1 confusing pair here: (1, 2).

The answer is 1. We update ans = 1.

Query 2:

The input is 0 3 2.

Decode id: ((0 + 1) Decode l: ((3 + 1) Decode r: ((2 + 1) We look at Reviewer 2's list from position 1 to 4: [2, 1, 4, 3].

There are 2 confusing pairs entirely within this range: (2, 1) and (4, 3).

The answer is 2. We update ans = 2.

Query 3:

The input is 0 3 1.

Decode id: ((0 + 2) Decode l: ((3 + 2) Decode r: ((1 + 2) We look at Reviewer 1's list from position 2 to 4: [2, 3, 4].

Game 2 is here, but Game 1 is not, so they cannot form a pair within this range. The only pair that fits entirely in this range is (3, 4).

The answer is 1.

N. [Light blue] Can you find the passion ?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Void has recently hit a mental block and is struggling to write competitive programming problems. To spark some ideas, he decides to visit an art museum.

The museum contains $$$n$$$ paintings. Each painting $$$i$$$ grants Void $$$a_i$$$ units of inspiration. There is also a global museum constant, $$$m$$$.

Void is very moody. Every day, he wakes up with a specific mood, represented by an integer $$$r$$$. On a day with mood $$$r$$$, Void will only look at paintings that satisfy the condition: $$$a_i \bmod m = r$$$. His total inspiration for the day will be the sum of the $$$a_i$$$ values of all paintings that satisfy this condition.

You are given $$$q$$$ queries, each representing a different day. For each query, Void needs at least $$$x$$$ units of total inspiration to write a problem, and he has a mood of $$$r$$$. Determine if Void will gather enough inspiration on each day.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10^5$$$) — denotes the number of paintings and the modulo constant.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — denotes the inspiration provided by each painting.

The third line contains a single integer $$$q$$$ ($$$1 \le q \le 10^5$$$) — denotes the number of queries.

The next $$$q$$$ lines each contain two integers $$$x$$$ and $$$r$$$ ($$$1 \le x \le 10^{14}$$$, $$$0 \le r \lt m$$$) — denotes the minimum required inspiration and Void's mood for that day.

Output

For each query, print "YES" (without quotes) if Void can gather at least $$$x$$$ units of inspiration. Otherwise, print "NO".

Example
Input
5 3
4 7 10 2 8
4
15 1
16 1
10 2
11 2
Output
YES
YES
YES
NO

O. [Light blue] Can you swim ?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Yamen is organizing a swimming competition for his n friends. The swimming pool has a total length of L meters.

The competition starts with all friends jumping from the starting blocks. Remarkably, they all hit the water at the exact same moment!

However, each friend has a different diving technique and swimming speed. Friend $$$i$$$ lands in the water exactly $$$d_i$$$ meters away from the starting block. From that exact point, they immediately begin swimming towards the finish line at a constant speed of $$$s_i$$$ meters per second.

Yamen wants to know who will win the race. The winner is the first person to reach or go past the Length of the pool.

If multiple friends reach the finish line at the exact same time, the friend with the smallest index (1-based) among them is declared the winner.

Given the pool length and the stats of each friend, determine the index of the winning friend.

Input

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

The first line of each test case contains two integers $$$n$$$ and $$$L$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le L \le 10^9$$$) — denotes the number of friends and the total length of the swimming pool in meters.

The following $$$n$$$ lines describe the friends. The $$$i$$$-th of these lines contains two integers $$$d_i$$$ and $$$s_i$$$ ($$$0 \le d_i \lt L$$$, $$$1 \le s_i \le 10^9$$$) — denotes the distance the $$$i$$$-th friend reaches upon hitting the water, and their swimming speed in meters per second.

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

Output

For each test case, output a single integer: the 1-based index of the friend who wins the competition.

Example
Input
3
3 100
10 2
20 1
0 3
2 50
20 5
14 6
2 10
7 1
8 2
Output
3
1
2