vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You are given an array of integers $a$ of length $n$. The elements of the array can be either different or the same.

Each element of the array is colored either blue or red. There are no unpainted elements in the array. One of the two operations described below can be applied to an array in a single step:

either you can select any blue element and decrease its value by $1$;

or you can select any red element and increase its value by $1$.

Situations in which there are no elements of some color at all are also possible. For example, if the whole array is colored blue or red, one of the operations becomes unavailable.

Determine whether it is possible to make $0$ or more steps such that the resulting array is a permutation of numbers from $1$ to $n$?

In other words, check whether there exists a sequence of steps (possibly empty) such that after applying it, the array $a$ contains in some order all numbers from $1$ to $n$ (inclusive), each exactly once.


-----Input-----

The first line contains an integer $t$ ($1 \leq t \leq 10^4$) — the number of input data sets in the test.

The description of each set of input data consists of three lines. The first line contains an integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the length of the original array $a$. The second line contains $n$ integers $a_1$, $a_2$, ..., $a_n$ ($-10^9 \leq a_i \leq 10^9$) — the array elements themselves.

The third line has length $n$ and consists exclusively of the letters 'B' and/or 'R': $i$th character is 'B' if $a_i$ is colored blue, and is 'R' if colored red.

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


-----Output-----

Print $t$ lines, each of which contains the answer to the corresponding test case of the input. Print YES as an answer if the corresponding array can be transformed into a permutation, and NO otherwise.

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


-----Examples-----

Input
8
4
1 2 5 2
BRBR
2
1 1
BB
5
3 1 4 2 5
RBRRB
5
3 1 3 1 3
RBRRB
5
5 1 5 1 5
RBRRB
4
2 2 2 2
BRBR
2
1 -2
BR
4
-2 -1 4 0
RRRR
Output
YES
NO
YES
YES
NO
YES
YES
YES


-----Note-----

In the first test case of the example, the following sequence of moves can be performed:

choose $i=3$, element $a_3=5$ is blue, so we decrease it, we get $a=[1,2,4,2]$;

choose $i=2$, element $a_2=2$ is red, so we increase it, we get $a=[1,3,4,2]$;

choose $i=3$, element $a_3=4$ is blue, so we decrease it, we get $a=[1,3,3,2]$;

choose $i=2$, element $a_2=2$ is red, so we increase it, we get $a=[1,4,3,2]$.

We got that $a$ is a permutation. Hence the answer is YES.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Madoka wants to enter to "Novosibirsk State University", but in the entrance exam she came across a very difficult task:

Given an integer $n$, it is required to calculate $\sum{\operatorname{lcm}(c, \gcd(a, b))}$, for all triples of positive integers $(a, b, c)$, where $a + b + c = n$.

In this problem $\gcd(x, y)$ denotes the greatest common divisor of $x$ and $y$, and $\operatorname{lcm}(x, y)$ denotes the least common multiple of $x$ and $y$.

Solve this problem for Madoka and help her to enter to the best university!


-----Input-----

The first and the only line contains a single integer $n$ ($3 \le n \le 10^5$).


-----Output-----

Print exactly one interger — $\sum{\operatorname{lcm}(c, \gcd(a, b))}$. Since the answer can be very large, then output it modulo $10^9 + 7$.


-----Examples-----

Input
3
Output
1
Input
5
Output
11
Input
69228
Output
778304278


-----Note-----

In the first example, there is only one suitable triple $(1, 1, 1)$. So the answer is $\operatorname{lcm}(1, \gcd(1, 1)) = \operatorname{lcm}(1, 1) = 1$.

In the second example, $\operatorname{lcm}(1, \gcd(3, 1)) + \operatorname{lcm}(1, \gcd(2, 2)) + \operatorname{lcm}(1, \gcd(1, 3)) + \operatorname{lcm}(2, \gcd(2, 1)) + \operatorname{lcm}(2, \gcd(1, 2)) + \operatorname{lcm}(3, \gcd(1, 1)) = \operatorname{lcm}(1, 1) + \operatorname{lcm}(1, 2) + \operatorname{lcm}(1, 1) + \operatorname{lcm}(2, 1) + \operatorname{lcm}(2, 1) + \operatorname{lcm}(3, 1) = 1 + 2 + 1 + 2 + 2 + 3 = 11$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Algorithmic predicament - Bug Fixing #9

Oh no! Timmy's algorithim has gone wrong! help Timmy fix his algorithim! 

Task
Your task is to fix timmy's algorithim so it returns the group name with the highest total age. 

You will receive two groups of `people` objects, with two properties `name` and `age`. The name property is a string and the age property is a number.  
Your goal is to make the total the age of all people having the same name through both groups and return the name of the one with the highest age. If two names have the same total age return the first alphabetical name.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Archaeologists found some information about an ancient land of Treeland. We know for sure that the Treeland consisted of n cities connected by the n - 1 road, such that you can get from each city to any other one along the roads. However, the information about the specific design of roads in Treeland has been lost. The only thing that the archaeologists can use is the preserved information about near cities.

Two cities of Treeland were called near, if it were possible to move from one city to the other one by moving through at most two roads. Also, a city is considered near to itself. During the recent excavations archaeologists found a set of n notes, each of them represents a list of cities, near to some of the n cities of the country. However, unfortunately, none of the found records lets you understand in what order the cities go in the list and for which city in the list the near to it cities were listed. 

Help the archaeologists and restore any variant of the map of Treeland that meets the found information.

Input

The first line contains integer n (2 ≤ n ≤ 1000) — the number of cities in the country. 

Next n lines describe the found lists of near cities. Each list starts from number k (1 ≤ k ≤ n), representing the number of cities in the list followed by k city numbers. All numbers in each list are distinct.

It is guaranteed that the given information determines at least one possible road map.

Output

Print n - 1 pairs of numbers representing the roads of the country. The i-th line must contain two integers ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi), showing that there is a road between cities ai and bi.

The answer you print must satisfy the description of close cities from the input. You may print the roads of the countries in any order. The cities that are connected by a road may also be printed in any order.

If there are multiple good answers, you may print any of them.

Examples

Input

5
4 3 2 4 1
5 5 3 2 4 1
5 4 2 1 5 3
4 2 1 4 3
3 1 4 5


Output

1 4
1 2
1 3
4 5


Input

6
5 6 1 3 4 2
5 2 1 3 4 6
6 3 6 2 5 4 1
6 6 1 2 5 3 4
3 5 2 4
5 3 1 2 4 6


Output

2 4
1 2
2 3
2 6
4 5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In fantasy hockey, there are $n$ team owners that each selects $k$ hockey players. To determine which owner gets which players, the owners hold a draft.

The draft proceeds as follows: the first owner may select any player, then the second owner can select any player except the player taken first and so on. In general, the current owner may take any player that has not been taken previously. Once all owners have selected one player, they repeat this process until all owners have selected $k$ players. No player may be selected by multiple teams.

Initially, all players are given a ranking based on how well they played in the previous year. However, the owners may not agree with this order. For example, the first owner may believe that the player which was ranked third in the previous year is the best player and would prefer to take them.

Each owner has a preference list. On their turn, the owner selects the player that is the highest available player on their own preference list. If all players on their preference list are taken, then they resort to using the ordering from the previous year.

Given the preference list of each owner and the rankings from the previous year, which players did each owner get?

-----Input-----
The first line of the input contains two integers $n$ ($1 \leq n \leq 60$), the number of owners, and $k$ ($1 \leq k \leq 1000$), the size of each team.

The next $n$ lines contain owners’ preferences in the order of drafting. Each line starts with an integer $q_ i$ ($0 \leq q_ i \leq 1500$), the size of the $i^\textrm {th}$ owners’ preference list. $q_ i$ names follow, separated by spaces, in order of $i^\textrm {th}$ owner’s preference. No name appears more than once in the $i^\textrm {th}$ owners’ list.

The next line contains a single integer $p$ ($n \cdot k \leq p \leq 65000$), indicating the number of players in the draft.

The next $p$ lines each contain a single name, they are ordered by their previous year’s ranking. Each player name is unique and comprised of at most $12$ letters of English alphabet.

The names in owners’ preference lists are guaranteed to appear in the player list.

-----Output-----
Display $n$ lines. The $i^\textrm {th}$ of which contains the $k$ names of the players that were selected by the $i^\textrm {th}$ owner. The $n$ teams should be in the original order of owners and players should be listed in the order in which they were drafted following the rules above.

-----Examples-----
Sample Input:
2 2
0
0
6
Shoresy
Jonesy
Reilly
Sholtzy
Fisky
Yorkie
Sample Output:
Shoresy Reilly
Jonesy Sholtzy

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Alice got tired of playing the tag game by the usual rules so she offered Bob a little modification to it. Now the game should be played on an undirected rooted tree of *n* vertices. Vertex 1 is the root of the tree.

Alice starts at vertex 1 and Bob starts at vertex *x* (*x*<=≠<=1). The moves are made in turns, Bob goes first. In one move one can either stay at the current vertex or travel to the neighbouring one.

The game ends when Alice goes to the same vertex where Bob is standing. Alice wants to minimize the total number of moves and Bob wants to maximize it.

You should write a program which will determine how many moves will the game last.

Input Specification:
The first line contains two integer numbers *n* and *x* (2<=≤<=*n*<=≤<=2·105, 2<=≤<=*x*<=≤<=*n*).

Each of the next *n*<=-<=1 lines contains two integer numbers *a* and *b* (1<=≤<=*a*,<=*b*<=≤<=*n*) — edges of the tree. It is guaranteed that the edges form a valid tree.

Output Specification:
Print the total number of moves Alice and Bob will make.

Demo Input:
['4 3\n1 2\n2 3\n2 4\n', '5 2\n1 2\n2 3\n3 4\n2 5\n']

Demo Output:
['4\n', '6\n']

Note:
In the first example the tree looks like this:

The red vertex is Alice's starting position, the blue one is Bob's. Bob will make the game run the longest by standing at the vertex 3 during all the game. So here are the moves:

B: stay at vertex 3

A: go to vertex 2

B: stay at vertex 3

A: go to vertex 3

In the second example the tree looks like this:

The moves in the optimal strategy are:

B: go to vertex 3

A: go to vertex 2

B: go to vertex 4

A: go to vertex 3

B: stay at vertex 4

A: go to vertex 4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Read problems statements in [Mandarin Chinese], [Russian], and [Bengali] as well.

A programming competition will be held in Chef's city which only accepts teams of size 2. At least one person in a team should know a programming language and at least one person should know about the English language. It is possible that one person in a team knows both programming and the English language. Then the qualification of the other teammate is not important i.e. he may or may not know programming and English. Now Chef has N students and wants to send *maximum* number of teams to the competition.

You are given an integer N and two binary strings S and T of length N. S_{i} =  '1' denotes that the i^{th} student knows a programming language, and S_{i} =  '0' denotes otherwise; similarly, T_{i} = '1' denotes that the i^{th} student knows English language, and T_{i} =  '0' denotes otherwise. Determine the maximum number of teams Chef can form.

------ Input Format ------ 

- The first line of input contains a single integer Q denoting the number of test cases. The description of Q test cases follows.
- Each test case contains 3 lines of input.
- The first line of each test case contains an integer N.
- The second line of each test case contains a string S.
- The last line of each test case contains a string T.

------ Output Format ------ 

For each test case, print a single line containing one integer - the maximum number of teams that Chef can form.

------ Constraints ------ 

$1 ≤ Q ≤ 1000$
$1 ≤ N ≤ 100$
$S$ and $T$ contains only characters '0' and '1'

----- Sample Input 1 ------ 
4
3
101
001
4
1010
0110
3
000
110
2
10
11

----- Sample Output 1 ------ 
1
2
0
1

----- explanation 1 ------ 
Test case $1$: The third student can team up with any other students as he knows both programming and English.

Test case $2$: The first two students make a team and the last two students make another team.

Test case $3$: No student knows how to program, hence there is no way to make a team.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Bike loves looking for the second maximum element in the sequence. The second maximum element in the sequence of distinct numbers *x*1,<=*x*2,<=...,<=*x**k* (*k*<=&gt;<=1) is such maximum element *x**j*, that the following inequality holds: .

The lucky number of the sequence of distinct positive integers *x*1,<=*x*2,<=...,<=*x**k* (*k*<=&gt;<=1) is the number that is equal to the bitwise excluding OR of the maximum element of the sequence and the second maximum element of the sequence.

You've got a sequence of distinct positive integers *s*1,<=*s*2,<=...,<=*s**n* (*n*<=&gt;<=1). Let's denote sequence *s**l*,<=*s**l*<=+<=1,<=...,<=*s**r* as *s*[*l*..*r*] (1<=≤<=*l*<=&lt;<=*r*<=≤<=*n*). Your task is to find the maximum number among all lucky numbers of sequences *s*[*l*..*r*].

Note that as all numbers in sequence *s* are distinct, all the given definitions make sence.

Input Specification:
The first line contains integer *n* (1<=&lt;<=*n*<=≤<=105). The second line contains *n* distinct integers *s*1,<=*s*2,<=...,<=*s**n* (1<=≤<=*s**i*<=≤<=109).

Output Specification:
Print a single integer — the maximum lucky number among all lucky numbers of sequences *s*[*l*..*r*].

Demo Input:
['5\n5 2 1 4 3\n', '5\n9 8 3 5 7\n']

Demo Output:
['7\n', '15\n']

Note:
For the first sample you can choose *s*[4..5] = {4, 3} and its lucky number is (4 *xor* 3) = 7. You can also choose *s*[1..2].

For the second sample you must choose *s*[2..5] = {8, 3, 5, 7}.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Piglet has got a birthday today. His friend Winnie the Pooh wants to make the best present for him — a honey pot. Of course Winnie realizes that he won't manage to get the full pot to Piglet. In fact, he is likely to eat all the honey from the pot. And as soon as Winnie planned a snack on is way, the pot should initially have as much honey as possible. 

The day before Winnie the Pooh replenished his honey stocks. Winnie-the-Pooh has n shelves at home, each shelf contains some, perhaps zero number of honey pots. During the day Winnie came to the honey shelves q times; on the i-th time he came to some shelf ui, took from it some pots ki, tasted the honey from each pot and put all those pots on some shelf vi. As Winnie chose the pots, he followed his intuition. And that means that among all sets of ki pots on shelf ui, he equiprobably chooses one.

Now Winnie remembers all actions he performed with the honey pots. He wants to take to the party the pot he didn't try the day before. For that he must know the mathematical expectation of the number m of shelves that don't have a single untasted pot. To evaluate his chances better, Winnie-the-Pooh wants to know the value m after each action he performs.

Your task is to write a program that will find those values for him.

Input

The first line of the input contains a single number n (1 ≤ n ≤ 105) — the number of shelves at Winnie's place. The second line contains n integers ai (1 ≤ i ≤ n, 0 ≤ ai ≤ 100) — the number of honey pots on a shelf number i. 

The next line contains integer q (1 ≤ q ≤ 105) — the number of actions Winnie did the day before. Then follow q lines, the i-th of them describes an event that follows chronologically; the line contains three integers ui, vi and ki (1 ≤ ui, vi ≤ n, 1 ≤ ki ≤ 5) — the number of the shelf from which Winnie took pots, the number of the shelf on which Winnie put the pots after he tasted each of them, and the number of the pots Winnie tasted, correspondingly.

Consider the shelves with pots numbered with integers from 1 to n. It is guaranteed that Winnie-the-Pooh Never tried taking more pots from the shelf than it has.

Output

For each Winnie's action print the value of the mathematical expectation m by the moment when this action is performed. The relative or absolute error of each value mustn't exceed 10 - 9.

Examples

Input

3
2 2 3
5
1 2 1
2 1 2
1 2 2
3 1 1
3 2 2


Output

0.000000000000
0.333333333333
1.000000000000
1.000000000000
2.000000000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Notice: unusual memory limit!

After the war, destroyed cities in the neutral zone were restored. And children went back to school.

The war changed the world, as well as education. In those hard days, a new math concept was created.

As we all know, logarithm function can be described as: $$$ log(p_1^{a_1}p_2^{a_2}...p_k^{a_2}) = a_1 log p_1 + a_2 log p_2 + ... + a_k log p_k  Where p_1^{a_1}p_2^{a_2}...p_k^{a_2}$$$ is the prime factorization of a integer. A problem is that the function uses itself in the definition. That is why it is hard to calculate.

So, the mathematicians from the neutral zone invented this: $$$ exlog_f(p_1^{a_1}p_2^{a_2}...p_k^{a_2}) = a_1 f(p_1) + a_2 f(p_2) + ... + a_k f(p_k) $$$

Notice that exlog_f(1) is always equal to 0.

This concept for any function f was too hard for children. So teachers told them that f can only be a polynomial of degree no more than 3 in daily uses (i.e., f(x) = Ax^3+Bx^2+Cx+D).

"Class is over! Don't forget to do your homework!" Here it is: $$$ ∑_{i=1}^n exlog_f(i) $$$

Help children to do their homework. Since the value can be very big, you need to find the answer modulo 2^{32}.

Input

The only line contains five integers n, A, B, C, and D (1 ≤ n ≤ 3 ⋅ 10^8, 0 ≤ A,B,C,D ≤ 10^6).

Output

Print the answer modulo 2^{32}.

Examples

Input

12 0 0 1 0


Output

63


Input

4 1 2 3 4


Output

136

Note

In the first sample:

exlog_f(1) = 0

exlog_f(2) = 2

exlog_f(3) = 3

exlog_f(4) = 2 + 2 = 4

exlog_f(5) = 5

exlog_f(6) = 2 + 3 = 5

exlog_f(7) = 7

exlog_f(8) = 2 + 2 + 2 = 6

exlog_f(9) = 3 + 3 = 6

exlog_f(10) = 2 + 5 = 7

exlog_f(11) = 11

exlog_f(12) = 2 + 2 + 3 = 7

 ∑_{i=1}^{12} exlog_f(i)=63 

In the second sample:

exlog_f(1) = 0

exlog_f(2) = (1 × 2^3 + 2 × 2^2 + 3 × 2 + 4) = 26

exlog_f(3) = (1 × 3^3 + 2 × 3^2 + 3 × 3 + 4) = 58

exlog_f(4) = 2 × exlog_f(2) = 52

 ∑_{i=1}^4 exlog_f(i)=0+26+58+52=136

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Ivan likes to learn different things about numbers, but he is especially interested in really big numbers. Ivan thinks that a positive integer number *x* is really big if the difference between *x* and the sum of its digits (in decimal representation) is not less than *s*. To prove that these numbers may have different special properties, he wants to know how rare (or not rare) they are — in fact, he needs to calculate the quantity of really big numbers that are not greater than *n*.

Ivan tried to do the calculations himself, but soon realized that it's too difficult for him. So he asked you to help him in calculations.

Input Specification:
The first (and the only) line contains two integers *n* and *s* (1<=≤<=*n*,<=*s*<=≤<=1018).

Output Specification:
Print one integer — the quantity of really big numbers that are not greater than *n*.

Demo Input:
['12 1\n', '25 20\n', '10 9\n']

Demo Output:
['3\n', '0\n', '1\n']

Note:
In the first example numbers 10, 11 and 12 are really big.

In the second example there are no really big numbers that are not greater than 25 (in fact, the first really big number is 30: 30 - 3 ≥ 20).

In the third example 10 is the only really big number (10 - 1 ≥ 9).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The marmots need to prepare k problems for HC^2 over n days. Each problem, once prepared, also has to be printed.

The preparation of a problem on day i (at most one per day) costs a_{i} CHF, and the printing of a problem on day i (also at most one per day) costs b_{i} CHF. Of course, a problem cannot be printed before it has been prepared (but doing both on the same day is fine).

What is the minimum cost of preparation and printing?


-----Input-----

The first line of input contains two space-separated integers n and k (1 ≤ k ≤ n ≤ 2200). The second line contains n space-separated integers a_1, ..., a_{n} ($1 \leq a_{i} \leq 10^{9}$) — the preparation costs. The third line contains n space-separated integers b_1, ..., b_{n} ($1 \leq b_{i} \leq 10^{9}$) — the printing costs.


-----Output-----

Output the minimum cost of preparation and printing k problems — that is, the minimum possible sum a_{i}_1 + a_{i}_2 + ... + a_{i}_{k} + b_{j}_1 + b_{j}_2 + ... + b_{j}_{k}, where 1 ≤ i_1 < i_2 < ... < i_{k} ≤ n, 1 ≤ j_1 < j_2 < ... < j_{k} ≤ n and i_1 ≤ j_1, i_2 ≤ j_2, ..., i_{k} ≤ j_{k}.


-----Example-----
Input
8 4
3 8 7 9 9 4 6 8
2 5 9 4 3 8 9 1

Output
32


-----Note-----

In the sample testcase, one optimum solution is to prepare the first problem on day 1 and print it on day 1, prepare the second problem on day 2 and print it on day 4, prepare the third problem on day 3 and print it on day 5, and prepare the fourth problem on day 6 and print it on day 8.

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