vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Better Documents Inc. is contemplating the next generation of word processors. Now, nearly every word processor includes a Spell Checker. BDI, however, is looking forward to replacing that with a true Typo Checker. We’ve all been caught, after relying on a spell checker, by typing mistakes (“typos”) that just happen to wind up as a correctly spelled word, just not the word we intended. BDI hopes to use AI to determine when a word’s context suggests that it is out of place and probably should have been a different, but similarly spelled, word.

As a first step in this process, they want to see how common such similar words really are in ordinary text. Write a program to read in paragraphs of text and to produce a list of similarly spelled words occurring in that text.

For the purpose of this program, a word is any maximal string of non-whitespace characters containing at least one alphabetic character. Whitespace can be either blanks or line terminators (“\r” or “\n”). The core of a word is what you have left after removing any non-alphabetic characters and replacing any upper-case alphabetic characters to their lower-case equivalents.

Two words are considered to be similarly spelled if the core of one word can be converted to the core of the other word by a single application of any one of the following transformations:
 - Delete a single character.
 - Insert a single alphabetic character.
 - Replace a single character by a different alphabetic character.
 - Transpose (exchange) any two adjacent characters.

-----Input-----
Input consists of $1$ to $100$ lines of text, followed by an end of input marker in the form of a line containing only the string “***”.

Each line of text will contain $0$ to $80$ ASCII characters (not counting line terminators).

-----Output-----
For each word core in the text that has one or more similarly spelled words, print a line consisting of
 - That word core
 - A colon (“:”) followed by a blank
 - A list of all similarly spelled word cores (with no duplicates and not containing the core to the left of the colons), in alphabetic order, separated by single spaces.

The lines printed should be in alphabetic order of the word cores to the left of the colon.

If there are no similarly spelled words in the input, print a single line containing the string “***”.

-----Examples-----
Sample Input 1:
Lost is Close to Lose

"Better Documents Inc. wants to add Typo Checking in to the
next generation of word processors," he said.
***
Sample Output 1:
close: lose
he: the
in: inc is
inc: in
is: in
lose: close lost
lost: lose
the: he

Sample Input 2:
The fox said, "When?"
"Not till 12 o'clock", replied the hen.
"That clock is stopped, it will never strike.", he said.
***
Sample Output 2:
clock: oclock
he: hen the
hen: he when
is: it
it: is
oclock: clock
the: he
till: will
when: hen
will: till

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The $String$ Family gave birth to a new $Tripartite$ $trio$ $sisters$ and named them $Hema$, $Rekha$ and $Sushma$. Hema and Rekha are very fond of parties whereas Sushma hates them. One day Hema and Rekha asked their parents to buy them candies to distribute to people in their birthday party. (Remember Hema, Rekha and Sushma were born on the same day). But Sushma was uninterested in the party and only wanted candies for herself.
You will be given a list $P$ of possible number of candidates coming to the party. Were $P[i]$ denotes the count of people coming in the i th possibility. In each case every person should get maximum possible equal number of candies  such that after distributing the candies, there are always $R$ candies remaining for Sushma. You have to calculate the minimum number of candies required to buy so that, in any possible situation of the given array, each person coming to party gets equal number of candies (at least 1 and maximum possible out of total) and there are always $R$ candies remaining for Sushma.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- First line of each test case contain  $N$, number of possible count of people coming to party
- Next line contain $N$ spaced integers denoting the count of people 
- Next line contain $R$ the number of candies always remaining after maximum equal distribution

-----Output:-----
For each testcase, output in a single line answer, the minimum number of candies required to buy.

-----Constraints-----
- $1 \leq T \leq 100$
- $1 \leq N \leq 10^4$
- $1 \leq P[i] \leq 41$
- $0 \leq R < min(P[i])$

-----Sample Input:-----
1
2
2 3
1

-----Sample Output:-----
7

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp is an organizer of a Berland ICPC regional event. There are n universities in Berland numbered from 1 to n. Polycarp knows all competitive programmers in the region. There are n students: the i-th student is enrolled at a university u_i and has a programming skill s_i.

Polycarp has to decide on the rules now. In particular, the number of members in the team.

Polycarp knows that if he chooses the size of the team to be some integer k, each university will send their k strongest (with the highest programming skill s) students in the first team, the next k strongest students in the second team and so on. If there are fewer than k students left, then the team can't be formed. Note that there might be universities that send zero teams.

The strength of the region is the total skill of the members of all present teams. If there are no teams present, then the strength is 0.

Help Polycarp to find the strength of the region for each choice of k from 1 to n.

Input

The first line contains a single integer t (1 ≤ t ≤ 1000) — the number of testcases.

The first line of each testcase contains a single integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the number of universities and the number of students.

The second line of each testcase contains n integers u_1, u_2, ..., u_n (1 ≤ u_i ≤ n) — the university the i-th student is enrolled at.

The third line of each testcase contains n integers s_1, s_2, ..., s_n (1 ≤ s_i ≤ 10^9) — the programming skill of the i-th student.

The sum of n over all testcases doesn't exceed 2 ⋅ 10^5.

Output

For each testcase print n integers: the strength of the region — the total skill of the members of the present teams — for each choice of team size k.

Example

Input


4
7
1 2 1 2 1 2 1
6 8 3 1 5 1 5
10
1 1 1 2 2 2 2 3 3 3
3435 3014 2241 2233 2893 2102 2286 2175 1961 2567
6
3 3 3 3 3 3
5 9 6 7 9 7
1
1
3083


Output


29 28 26 19 0 0 0 
24907 20705 22805 9514 0 0 0 0 0 0 
43 43 43 32 38 43 
3083 

Note

In the first testcase the teams from each university for each k are: 

  * k=1: 
    * university 1: [6], [5], [5], [3]; 
    * university 2: [8], [1], [1]; 
  * k=2: 
    * university 1: [6, 5], [5, 3]; 
    * university 2: [8, 1]; 
  * k=3: 
    * university 1: [6, 5, 5]; 
    * university 2: [8, 1, 1]; 
  * k=4: 
    * university 1: [6, 5, 5, 3]; 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Petya and Divisors

Time Limit: 5 seconds

Memory Limit: 256 megabytes

Problem Description:
Little Petya loves looking for numbers' divisors. One day Petya came across the following problem:

You are given *n* queries in the form "*x**i* *y**i*". For each query Petya should count how many divisors of number *x**i* divide none of the numbers *x**i*<=-<=*y**i*,<=*x**i*<=-<=*y**i*<=+<=1,<=...,<=*x**i*<=-<=1. Help him.

Input Specification:
The first line contains an integer *n* (1<=≤<=*n*<=≤<=105). Each of the following *n* lines contain two space-separated integers *x**i* and *y**i* (1<=≤<=*x**i*<=≤<=105, 0<=≤<=*y**i*<=≤<=*i*<=-<=1, where *i* is the query's ordinal number; the numeration starts with 1). 

If *y**i*<==<=0 for the query, then the answer to the query will be the number of divisors of the number *x**i*. In this case you do not need to take the previous numbers *x* into consideration.

Output Specification:
For each query print the answer on a single line: the number of positive integers *k* such that 

Demo Input:
['6\n4 0\n3 1\n5 2\n6 2\n18 4\n10000 3\n']

Demo Output:
['3\n1\n1\n2\n2\n22\n']

Note:
Let's write out the divisors that give answers for the first 5 queries:

1) 1, 2, 4 

2) 3

3) 5

4) 2, 6

5) 9, 18

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Rounding

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Vasya has a non-negative integer *n*. He wants to round it to nearest integer, which ends up with 0. If *n* already ends up with 0, Vasya considers it already rounded.

For example, if *n*<==<=4722 answer is 4720. If *n*<==<=5 Vasya can round it to 0 or to 10. Both ways are correct.

For given *n* find out to which integer will Vasya round it.

Input Specification:
The first line contains single integer *n* (0<=≤<=*n*<=≤<=109) — number that Vasya has.

Output Specification:
Print result of rounding *n*. Pay attention that in some cases answer isn't unique. In that case print any correct answer.

Demo Input:
['5\n', '113\n', '1000000000\n', '5432359\n']

Demo Output:
['0\n', '110\n', '1000000000\n', '5432360\n']

Note:
In the first example *n* = 5. Nearest integers, that ends up with zero are 0 and 10. Any of these answers is correct, so you can print 0 or 10.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are in the future. It's the time of autonomous cars. Switching lanes is a pretty difficult task for autonomous cars, and you have the logs from an experiment you had run with two cars. You want to verify whether the logs are corrupted, or could be valid.
In that experiment, you had a highway consisting of two lanes. These were represented by 2 rows of an infinite grid. The cell (1, 1) is the top left cell which is the starting point of the first lane. Cell (2, 1) is the bottom left cell of the grid which is the starting point of the second lane.
There are two cars, 1 and 2 that start from the cell (1, 1) and (2, 1). 
At each instant, a car has the following choices.
- Stay at the current position.
- Move one cell to the right.
- Switch Lanes. When a car switches its lane, it stays in the same column. That is, from (1, i) it could go to (2, i), or from (2, i) it could go to (1, i). But both both cars shouldn't end up at the same cell at any point. Note that there could have been a car which had moved at the very instant that you move into it.
Consider one such scenario of driving cars.
Time $t = 0$
1.....
2.....

Time $t = 1$. Car 2 advances one cell right. Car 1 stays at the same place.
1.....
.2....

Time $t = 2$. Car 2 stays at its place. Car 1 switches the lane.
......
12....

Time $t = 3$. Car 2 moves one cell to the right.  Car 1 also moves one cell to the right.
......
.12...

Time $t = 4$. Both the cars stay in the same place.
......
.12...

You are given positions of the car at $n$ instants. Your task is to check whether this situation is feasible or not.

-----Input-----
- The first line of the input contains an integer $T$ denoting the number of test cases. The description of the test cases follows.
- The first line of each test case contains an integer $n$ denoting the number of instants where the positions of the cars were recorded.
- Each of next $n$ lines contains 5 space separated integers denoting $t_i, x_i, y_i, X_i, Y_i$ denoting time, $x$ and $y$ coordinate of the first car, and that of second car.

-----Output-----
For each test case, output either yes or no according to the answer to the problem.

-----Constraints-----
- $1 \le T \le 10^5$
- $1 \le n \leq 10^5$
- $1 \le t_i, y_i, X_i, Y_i \leq 10^9$
- $1 \leq x_i \leq 2$
- $t_i < t_{i+1}$
- Sum of $n$ over all the test cases doesn't exceed $10^6$

-----Example Input-----
2
3
1 1 1 2 2
2 2 1 2 2
4 2 2 2 3
1
1 1 3 2 2

-----Example Output-----
yes
no

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
<image>

To monitor cryptocurrency exchange rates trader William invented a wonderful device consisting of n lights arranged in a row. The device functions in the following way:

Initially, all lights on William's device are turned off. At the beginning of a new iteration the device randomly, with a uniform distribution, picks a light that is turned off and turns it on, telling William which cryptocurrency he should invest in. After this iteration if any k consecutive lights contain more than one turned on light, then the device finishes working.

William doesn't like uncertainty, so he wants you to calculate the expected value of the number of lights that are turned on in the device after it finishes working.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 10). Description of the test cases follows.

The only line for each test case contains two integers n and k (2 ≤ k ≤ n ≤ 10^5), which are the total number of lights and the length of subsegment of lights that are being checked, respectively.

Output

For each test case print the answer, modulo 10^9+7. 

Formally, let M = 10^9+7. It can be shown that the answer can be expressed as an irreducible fraction p/q, where p and q are integers and q not ≡ 0 \pmod{M}. Output the integer equal to p ⋅ q^{-1} mod M. In other words, output such an integer x that 0 ≤ x < M and x ⋅ q ≡ p \pmod{M}.

Example

Input


3
3 2
15 2
40 15


Output


333333338
141946947
329622137

Note

Explanation of the first sample test case:

Let's write out all possible sequences of light toggles, which will make the device complete its operation:

  1. (1, 2) — 2 lights are turned on 
  2. (1, 3, 2) — 3 lights are turned on 
  3. (2, 1) — 2 lights are turned on 
  4. (2, 3) — 2 lights are turned on 
  5. (3, 2) — 2 lights are turned on 
  6. (3, 1, 2) — 3 lights are turned on 



Then the final expected value will be equal to 2/6 + 3/6 + 2/6 + 2/6 + 2/6 + 3/6 = 14/6 = 7/3. 

Then the required output will be 333333338, since 333333338 ⋅ 3 ≡ 7 \pmod{10^9+7}.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two circles. Find the area of their intersection.


-----Input-----

The first line contains three integers x_1, y_1, r_1 ( - 10^9 ≤ x_1, y_1 ≤ 10^9, 1 ≤ r_1 ≤ 10^9) — the position of the center and the radius of the first circle.

The second line contains three integers x_2, y_2, r_2 ( - 10^9 ≤ x_2, y_2 ≤ 10^9, 1 ≤ r_2 ≤ 10^9) — the position of the center and the radius of the second circle.


-----Output-----

Print the area of the intersection of the circles. The answer will be considered correct if the absolute or relative error doesn't exceed 10^{ - 6}.


-----Examples-----
Input
0 0 4
6 0 4

Output
7.25298806364175601379

Input
0 0 5
11 0 5

Output
0.00000000000000000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is an infinite 2-dimensional grid. The robot stands in cell $(0, 0)$ and wants to reach cell $(x, y)$. Here is a list of possible commands the robot can execute:

move north from cell $(i, j)$ to $(i, j + 1)$;

move east from cell $(i, j)$ to $(i + 1, j)$;

move south from cell $(i, j)$ to $(i, j - 1)$;

move west from cell $(i, j)$ to $(i - 1, j)$;

stay in cell $(i, j)$.

The robot wants to reach cell $(x, y)$ in as few commands as possible. However, he can't execute the same command two or more times in a row.

What is the minimum number of commands required to reach $(x, y)$ from $(0, 0)$?


-----Input-----

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

Each of the next $t$ lines contains two integers $x$ and $y$ ($0 \le x, y \le 10^4$) — the destination coordinates of the robot.


-----Output-----

For each testcase print a single integer — the minimum number of commands required for the robot to reach $(x, y)$ from $(0, 0)$ if no command is allowed to be executed two or more times in a row.


-----Examples-----

Input
5
5 5
3 4
7 1
0 0
2 0
Output
10
7
13
0
3


-----Note-----

The explanations for the example test:

We use characters N, E, S, W and 0 to denote going north, going east, going south, going west and staying in the current cell, respectively.

In the first test case, the robot can use the following sequence: NENENENENE.

In the second test case, the robot can use the following sequence: NENENEN.

In the third test case, the robot can use the following sequence: ESENENE0ENESE.

In the fourth test case, the robot doesn't need to go anywhere at all.

In the fifth test case, the robot can use the following sequence: E0E.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In 2020, AtCoder Inc. with an annual sales of more than one billion yen (the currency of Japan) has started a business in programming education.

One day, there was an exam where a one-year-old child must write a program that prints Hello World, and a two-year-old child must write a program that receives integers A, B and prints A+B.

Takahashi, who is taking this exam, suddenly forgets his age.

He decides to write a program that first receives his age N (1 or 2) as input, then prints Hello World if N=1, and additionally receives integers A, B and prints A+B if N=2.

Write this program for him.  

-----Constraints-----
 - N is 1 or 2.
 - A is an integer between 1 and 9 (inclusive).
 - B is an integer between 1 and 9 (inclusive).

-----Input-----
Input is given from Standard Input in one of the following formats:  
1

2
A
B

-----Output-----
If N=1, print Hello World; if N=2, print A+B.  

-----Sample Input-----
1

-----Sample Output-----
Hello World

As N=1, Takahashi is one year old. Thus, we should print Hello World.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a keypad as shown in the diagram, and an N digit number which is represented by array a[ ], the task is to list all words which are possible by pressing these numbers.
Example 1:
Input: N = 3, a[] = {2, 3, 4}
Output:
adg adh adi aeg aeh aei afg afh afi 
bdg bdh bdi beg beh bei bfg bfh bfi 
cdg cdh cdi ceg ceh cei cfg cfh cfi 
Explanation: When we press 2,3,4 then 
adg, adh, adi, ... cfi are the list of 
possible words.
Example 2:
Input: N = 3, a[] = {3, 4, 5}
Output:
dgj dgk dgl dhj dhk dhl dij dik dil 
egj egk egl ehj ehk ehl eij eik eil 
fgj fgk fgl fhj fhk fhl fij fik fil
Explanation: When we press 3,4,5 then 
dgj, dgk, dgl, ... fil are the list of 
possible words.
Your Task:
You don't need to read input or print anything. You just need to complete the function possibleWords() that takes an array a[ ] and N as input parameters and returns an array of all the possible words in lexicographical increasing order. 
Expected Time Complexity: O(4^{N}^{ }* N).
Expected Auxiliary Space: O(N).
Constraints:
1 ≤ N ≤ 10
2 ≤ a[i] ≤ 9

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Kefa and Company

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Kefa wants to celebrate his first big salary by going to restaurant. However, he needs company. 

Kefa has *n* friends, each friend will agree to go to the restaurant if Kefa asks. Each friend is characterized by the amount of money he has and the friendship factor in respect to Kefa. The parrot doesn't want any friend to feel poor compared to somebody else in the company (Kefa doesn't count). A friend feels poor if in the company there is someone who has at least *d* units of money more than he does. Also, Kefa wants the total friendship factor of the members of the company to be maximum. Help him invite an optimal company!

Input Specification:
The first line of the input contains two space-separated integers, *n* and *d* (1<=≤<=*n*<=≤<=105, ) — the number of Kefa's friends and the minimum difference between the amount of money in order to feel poor, respectively.

Next *n* lines contain the descriptions of Kefa's friends, the (*i*<=+<=1)-th line contains the description of the *i*-th friend of type *m**i*, *s**i* (0<=≤<=*m**i*,<=*s**i*<=≤<=109) — the amount of money and the friendship factor, respectively.

Output Specification:
Print the maximum total friendship factir that can be reached.

Demo Input:
['4 5\n75 5\n0 100\n150 20\n75 1\n', '5 100\n0 7\n11 32\n99 10\n46 8\n87 54\n']

Demo Output:
['100\n', '111\n']

Note:
In the first sample test the most profitable strategy is to form a company from only the second friend. At all other variants the total degree of friendship will be worse.

In the second sample test we can take all the friends.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
As you could know there are no male planes nor female planes. However, each plane on Earth likes some other plane. There are n planes on Earth, numbered from 1 to n, and the plane with number i likes the plane with number f_{i}, where 1 ≤ f_{i} ≤ n and f_{i} ≠ i.

We call a love triangle a situation in which plane A likes plane B, plane B likes plane C and plane C likes plane A. Find out if there is any love triangle on Earth.


-----Input-----

The first line contains a single integer n (2 ≤ n ≤ 5000) — the number of planes.

The second line contains n integers f_1, f_2, ..., f_{n} (1 ≤ f_{i} ≤ n, f_{i} ≠ i), meaning that the i-th plane likes the f_{i}-th.


-----Output-----

Output «YES» if there is a love triangle consisting of planes on Earth. Otherwise, output «NO».

You can output any letter in lower case or in upper case.


-----Examples-----
Input
5
2 4 5 1 3

Output
YES

Input
5
5 5 5 5 1

Output
NO



-----Note-----

In first example plane 2 likes plane 4, plane 4 likes plane 1, plane 1 likes plane 2 and that is a love triangle.

In second example there are no love triangles.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.