meetforever/GRPO_CL huggingface dataset:
user: Igor is a post-graduate student of chemistry faculty in Berland State University (BerSU). He needs to conduct a complicated experiment to write his thesis, but laboratory of BerSU doesn't contain all the materials required for this experiment.

Fortunately, chemical laws allow material transformations (yes, chemistry in Berland differs from ours). But the rules of transformation are a bit strange.

Berland chemists are aware of n materials, numbered in the order they were discovered. Each material can be transformed into some other material (or vice versa). Formally, for each i (2 ≤ i ≤ n) there exist two numbers x_{i} and k_{i} that denote a possible transformation: k_{i} kilograms of material x_{i} can be transformed into 1 kilogram of material i, and 1 kilogram of material i can be transformed into 1 kilogram of material x_{i}. Chemical processing equipment in BerSU allows only such transformation that the amount of resulting material is always an integer number of kilograms.

For each i (1 ≤ i ≤ n) Igor knows that the experiment requires a_{i} kilograms of material i, and the laboratory contains b_{i} kilograms of this material. Is it possible to conduct an experiment after transforming some materials (or none)?


-----Input-----

The first line contains one integer number n (1 ≤ n ≤ 10^5) — the number of materials discovered by Berland chemists.

The second line contains n integer numbers b_1, b_2... b_{n} (1 ≤ b_{i} ≤ 10^12) — supplies of BerSU laboratory.

The third line contains n integer numbers a_1, a_2... a_{n} (1 ≤ a_{i} ≤ 10^12) — the amounts required for the experiment.

Then n - 1 lines follow. j-th of them contains two numbers x_{j} + 1 and k_{j} + 1 that denote transformation of (j + 1)-th material (1 ≤ x_{j} + 1 ≤ j, 1 ≤ k_{j} + 1 ≤ 10^9).


-----Output-----

Print YES if it is possible to conduct an experiment. Otherwise print NO.


-----Examples-----
Input
3
1 2 3
3 2 1
1 1
1 1

Output
YES

Input
3
3 2 1
1 2 3
1 1
1 2

Output
NO
user: It is the middle of 2018 and Maria Stepanovna, who lives outside Krasnokamensk (a town in Zabaikalsky region), wants to rent three displays to highlight an important problem.

There are $n$ displays placed along a road, and the $i$-th of them can display a text with font size $s_i$ only. Maria Stepanovna wants to rent such three displays with indices $i < j < k$ that the font size increases if you move along the road in a particular direction. Namely, the condition $s_i < s_j < s_k$ should be held.

The rent cost is for the $i$-th display is $c_i$. Please determine the smallest cost Maria Stepanovna should pay.


-----Input-----

The first line contains a single integer $n$ ($3 \le n \le 3\,000$) — the number of displays.

The second line contains $n$ integers $s_1, s_2, \ldots, s_n$ ($1 \le s_i \le 10^9$) — the font sizes on the displays in the order they stand along the road.

The third line contains $n$ integers $c_1, c_2, \ldots, c_n$ ($1 \le c_i \le 10^8$) — the rent costs for each display.


-----Output-----

If there are no three displays that satisfy the criteria, print -1. Otherwise print a single integer — the minimum total rent cost of three displays with indices $i < j < k$ such that $s_i < s_j < s_k$.


-----Examples-----
Input
5
2 4 5 4 10
40 30 20 10 40

Output
90

Input
3
100 101 100
2 4 5

Output
-1

Input
10
1 2 3 4 5 6 7 8 9 10
10 13 11 14 15 12 13 13 18 13

Output
33



-----Note-----

In the first example you can, for example, choose displays $1$, $4$ and $5$, because $s_1 < s_4 < s_5$ ($2 < 4 < 10$), and the rent cost is $40 + 10 + 40 = 90$.

In the second example you can't select a valid triple of indices, so the answer is -1.
user: You've got an array, consisting of n integers a_1, a_2, ..., a_{n}. Also, you've got m queries, the i-th query is described by two integers l_{i}, r_{i}. Numbers l_{i}, r_{i} define a subsegment of the original array, that is, the sequence of numbers a_{l}_{i}, a_{l}_{i} + 1, a_{l}_{i} + 2, ..., a_{r}_{i}. For each query you should check whether the corresponding segment is a ladder. 

A ladder is a sequence of integers b_1, b_2, ..., b_{k}, such that it first doesn't decrease, then doesn't increase. In other words, there is such integer x (1 ≤ x ≤ k), that the following inequation fulfills: b_1 ≤ b_2 ≤ ... ≤ b_{x} ≥ b_{x} + 1 ≥ b_{x} + 2... ≥ b_{k}. Note that the non-decreasing and the non-increasing sequences are also considered ladders.


-----Input-----

The first line contains two integers n and m (1 ≤ n, m ≤ 10^5) — the number of array elements and the number of queries. The second line contains the sequence of integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9), where number a_{i} stands for the i-th array element.

The following m lines contain the description of the queries. The i-th line contains the description of the i-th query, consisting of two integers l_{i}, r_{i} (1 ≤ l_{i} ≤ r_{i} ≤ n) — the boundaries of the subsegment of the initial array.

The numbers in the lines are separated by single spaces.


-----Output-----

Print m lines, in the i-th line print word "Yes" (without the quotes), if the subsegment that corresponds to the i-th query is the ladder, or word "No" (without the quotes) otherwise. 


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

Output
Yes
Yes
No
Yes
No
Yes
user: Dreamoon likes to play with sets, integers and $gcd$. $\operatorname{gcd}(a, b)$ is defined as the largest positive integer that divides both a and b.

Let S be a set of exactly four distinct integers greater than 0. Define S to be of rank k if and only if for all pairs of distinct elements s_{i}, s_{j} from S, $\operatorname{gcd}(s_{i}, s_{j}) = k$.

Given k and n, Dreamoon wants to make up n sets of rank k using integers from 1 to m such that no integer is used in two different sets (of course you can leave some integers without use). Calculate the minimum m that makes it possible and print one possible solution.


-----Input-----

The single line of the input contains two space separated integers n, k (1 ≤ n ≤ 10 000, 1 ≤ k ≤ 100).


-----Output-----

On the first line print a single integer — the minimal possible m. 

On each of the next n lines print four space separated integers representing the i-th set.

Neither the order of the sets nor the order of integers within a set is important. If there are multiple possible solutions with minimal m, print any one of them.


-----Examples-----
Input
1 1

Output
5
1 2 3 5

Input
2 2

Output
22
2 4 6 22
14 18 10 16



-----Note-----

For the first example it's easy to see that set {1, 2, 3, 4} isn't a valid set of rank 1 since $\operatorname{gcd}(2,4) = 2 \neq 1$.
user: Arseniy is already grown-up and independent. His mother decided to leave him alone for m days and left on a vacation. She have prepared a lot of food, left some money and washed all Arseniy's clothes. 

Ten minutes before her leave she realized that it would be also useful to prepare instruction of which particular clothes to wear on each of the days she will be absent. Arseniy's family is a bit weird so all the clothes is enumerated. For example, each of Arseniy's n socks is assigned a unique integer from 1 to n. Thus, the only thing his mother had to do was to write down two integers l_{i} and r_{i} for each of the days — the indices of socks to wear on the day i (obviously, l_{i} stands for the left foot and r_{i} for the right). Each sock is painted in one of k colors.

When mother already left Arseniy noticed that according to instruction he would wear the socks of different colors on some days. Of course, that is a terrible mistake cause by a rush. Arseniy is a smart boy, and, by some magical coincidence, he posses k jars with the paint — one for each of k colors.

Arseniy wants to repaint some of the socks in such a way, that for each of m days he can follow the mother's instructions and wear the socks of the same color. As he is going to be very busy these days he will have no time to change the colors of any socks so he has to finalize the colors now.

The new computer game Bota-3 was just realised and Arseniy can't wait to play it. What is the minimum number of socks that need their color to be changed in order to make it possible to follow mother's instructions and wear the socks of the same color during each of m days.


-----Input-----

The first line of input contains three integers n, m and k (2 ≤ n ≤ 200 000, 0 ≤ m ≤ 200 000, 1 ≤ k ≤ 200 000) — the number of socks, the number of days and the number of available colors respectively.

The second line contain n integers c_1, c_2, ..., c_{n} (1 ≤ c_{i} ≤ k) — current colors of Arseniy's socks.

Each of the following m lines contains two integers l_{i} and r_{i} (1 ≤ l_{i}, r_{i} ≤ n, l_{i} ≠ r_{i}) — indices of socks which Arseniy should wear during the i-th day.


-----Output-----

Print one integer — the minimum number of socks that should have their colors changed in order to be able to obey the instructions and not make people laugh from watching the socks of different colors.


-----Examples-----
Input
3 2 3
1 2 3
1 2
2 3

Output
2

Input
3 2 2
1 1 2
1 2
2 1

Output
0



-----Note-----

In the first sample, Arseniy can repaint the first and the third socks to the second color.

In the second sample, there is no need to change any colors.
user: A lot of frogs want to cross a river. A river is $w$ units width, but frogs can only jump $l$ units long, where $l < w$. Frogs can also jump on lengths shorter than $l$. but can't jump longer. Hopefully, there are some stones in the river to help them.

The stones are located at integer distances from the banks. There are $a_i$ stones at the distance of $i$ units from the bank the frogs are currently at. Each stone can only be used once by one frog, after that it drowns in the water.

What is the maximum number of frogs that can cross the river, given that then can only jump on the stones?


-----Input-----

The first line contains two integers $w$ and $l$ ($1 \le l < w \le 10^5$) — the width of the river and the maximum length of a frog's jump.

The second line contains $w - 1$ integers $a_1, a_2, \ldots, a_{w-1}$ ($0 \le a_i \le 10^4$), where $a_i$ is the number of stones at the distance $i$ from the bank the frogs are currently at.


-----Output-----

Print a single integer — the maximum number of frogs that can cross the river.


-----Examples-----
Input
10 5
0 0 1 0 2 0 0 1 0

Output
3

Input
10 3
1 1 1 1 2 1 1 1 1

Output
3



-----Note-----

In the first sample two frogs can use the different stones at the distance $5$, and one frog can use the stones at the distances $3$ and then $8$.

In the second sample although there are two stones at the distance $5$, that does not help. The three paths are: $0 \to 3 \to 6 \to 9 \to 10$, $0 \to 2 \to 5 \to 8 \to 10$, $0 \to 1 \to 4 \to 7 \to 10$.
user: Professor GukiZ has two arrays of integers, a and b. Professor wants to make the sum of the elements in the array a s_{a} as close as possible to the sum of the elements in the array b s_{b}. So he wants to minimize the value v = |s_{a} - s_{b}|.

In one operation professor can swap some element from the array a and some element from the array b. For example if the array a is [5, 1, 3, 2, 4] and the array b is [3, 3, 2] professor can swap the element 5 from the array a and the element 2 from the array b and get the new array a [2, 1, 3, 2, 4] and the new array b [3, 3, 5].

Professor doesn't want to make more than two swaps. Find the minimal value v and some sequence of no more than two swaps that will lead to the such value v. Professor makes swaps one by one, each new swap he makes with the new arrays a and b.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 2000) — the number of elements in the array a.

The second line contains n integers a_{i} ( - 10^9 ≤ a_{i} ≤ 10^9) — the elements of the array a.

The third line contains integer m (1 ≤ m ≤ 2000) — the number of elements in the array b.

The fourth line contains m integers b_{j} ( - 10^9 ≤ b_{j} ≤ 10^9) — the elements of the array b.


-----Output-----

In the first line print the minimal value v = |s_{a} - s_{b}| that can be got with no more than two swaps.

The second line should contain the number of swaps k (0 ≤ k ≤ 2).

Each of the next k lines should contain two integers x_{p}, y_{p} (1 ≤ x_{p} ≤ n, 1 ≤ y_{p} ≤ m) — the index of the element in the array a and the index of the element in the array b in the p-th swap.

If there are several optimal solutions print any of them. Print the swaps in order the professor did them.


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

Output
1
2
1 1
4 2

Input
5
1 2 3 4 5
1
15

Output
0
0

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

Output
1
1
3 1
user: Polycarp plays a well-known computer game (we won't mention its name). In this game, he can craft tools of two types — shovels and swords. To craft a shovel, Polycarp spends two sticks and one diamond; to craft a sword, Polycarp spends two diamonds and one stick.

Each tool can be sold for exactly one emerald. How many emeralds can Polycarp earn, if he has $a$ sticks and $b$ diamonds?


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 1000$) — the number of test cases.

The only line of each test case contains two integers $a$ and $b$ ($0 \le a, b \le 10^9$) — the number of sticks and the number of diamonds, respectively.


-----Output-----

For each test case print one integer — the maximum number of emeralds Polycarp can earn.


-----Example-----
Input
4
4 4
1000000000 0
7 15
8 7

Output
2
0
7
5



-----Note-----

In the first test case Polycarp can earn two emeralds as follows: craft one sword and one shovel.

In the second test case Polycarp does not have any diamonds, so he cannot craft anything.
user: The government of Berland decided to improve network coverage in his country. Berland has a unique structure: the capital in the center and $n$ cities in a circle around the capital. The capital already has a good network coverage (so the government ignores it), but the $i$-th city contains $a_i$ households that require a connection.

The government designed a plan to build $n$ network stations between all pairs of neighboring cities which will maintain connections only for these cities. In other words, the $i$-th network station will provide service only for the $i$-th and the $(i + 1)$-th city (the $n$-th station is connected to the $n$-th and the $1$-st city).

All network stations have capacities: the $i$-th station can provide the connection to at most $b_i$ households.

Now the government asks you to check can the designed stations meet the needs of all cities or not — that is, is it possible to assign each household a network station so that each network station $i$ provides the connection to at most $b_i$ households.


-----Input-----

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

The first line of each test case contains the single integer $n$ ($2 \le n \le 10^6$) — the number of cities and stations.

The second line of each test case contains $n$ integers ($1 \le a_i \le 10^9$) — the number of households in the $i$-th city.

The third line of each test case contains $n$ integers ($1 \le b_i \le 10^9$) — the capacities of the designed stations.

It's guaranteed that the sum of $n$ over test cases doesn't exceed $10^6$.


-----Output-----

For each test case, print YES, if the designed stations can meet the needs of all cities, or NO otherwise (case insensitive).


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

Output
YES
YES
NO
YES
YES



-----Note-----

In the first test case:   the first network station can provide $2$ connections to the first city and $1$ connection to the second city;  the second station can provide $2$ connections to the second city and $1$ connection to the third city;  the third station can provide $3$ connections to the third city. 

In the second test case:   the $1$-st station can provide $2$ connections to the $1$-st city;  the $2$-nd station can provide $3$ connections to the $2$-nd city;  the $3$-rd station can provide $3$ connections to the $3$-rd city and $1$ connection to the $1$-st station. 

In the third test case, the fourth city needs $5$ connections, but the third and the fourth station has $4$ connections in total.
user: Gottfried learned about binary number representation. He then came up with this task and presented it to you.

You are given a collection of $n$ non-negative integers $a_1, \ldots, a_n$. You are allowed to perform the following operation: choose two distinct indices $1 \leq i, j \leq n$. If before the operation $a_i = x$, $a_j = y$, then after the operation $a_i = x~\mathsf{AND}~y$, $a_j = x~\mathsf{OR}~y$, where $\mathsf{AND}$ and $\mathsf{OR}$ are bitwise AND and OR respectively (refer to the Notes section for formal description). The operation may be performed any number of times (possibly zero).

After all operations are done, compute $\sum_{i=1}^n a_i^2$ — the sum of squares of all $a_i$. What is the largest sum of squares you can achieve?


-----Input-----

The first line contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$).

The second line contains $n$ integers $a_1, \ldots, a_n$ ($0 \leq a_i < 2^{20}$).


-----Output-----

Print a single integer — the largest possible sum of squares that can be achieved after several (possibly zero) operations.


-----Examples-----
Input
1
123

Output
15129

Input
3
1 3 5

Output
51

Input
2
349525 699050

Output
1099509530625



-----Note-----

In the first sample no operation can be made, thus the answer is $123^2$.

In the second sample we can obtain the collection $1, 1, 7$, and $1^2 + 1^2 + 7^2 = 51$.

If $x$ and $y$ are represented in binary with equal number of bits (possibly with leading zeros), then each bit of $x~\mathsf{AND}~y$ is set to $1$ if and only if both corresponding bits of $x$ and $y$ are set to $1$. Similarly, each bit of $x~\mathsf{OR}~y$ is set to $1$ if and only if at least one of the corresponding bits of $x$ and $y$ are set to $1$. For example, $x = 3$ and $y = 5$ are represented as $011_2$ and $101_2$ (highest bit first). Then, $x~\mathsf{AND}~y = 001_2 = 1$, and $x~\mathsf{OR}~y = 111_2 = 7$.
user: A very brave explorer Petya once decided to explore Paris catacombs. Since Petya is not really experienced, his exploration is just walking through the catacombs.

Catacombs consist of several rooms and bidirectional passages between some pairs of them. Some passages can connect a room to itself and since the passages are built on different depths they do not intersect each other. Every minute Petya arbitrary chooses a passage from the room he is currently in and then reaches the room on the other end of the passage in exactly one minute. When he enters a room at minute i, he makes a note in his logbook with number t_{i}:   If Petya has visited this room before, he writes down the minute he was in this room last time;  Otherwise, Petya writes down an arbitrary non-negative integer strictly less than current minute i. 

Initially, Petya was in one of the rooms at minute 0, he didn't write down number t_0.

At some point during his wandering Petya got tired, threw out his logbook and went home. Vasya found his logbook and now he is curious: what is the minimum possible number of rooms in Paris catacombs according to Petya's logbook?


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 2·10^5) — then number of notes in Petya's logbook.

The second line contains n non-negative integers t_1, t_2, ..., t_{n} (0 ≤ t_{i} < i) — notes in the logbook.


-----Output-----

In the only line print a single integer — the minimum possible number of rooms in Paris catacombs.


-----Examples-----
Input
2
0 0

Output
2

Input
5
0 1 0 1 3

Output
3



-----Note-----

In the first sample, sequence of rooms Petya visited could be, for example 1 → 1 → 2, 1 → 2 → 1 or 1 → 2 → 3. The minimum possible number of rooms is 2.

In the second sample, the sequence could be 1 → 2 → 3 → 1 → 2 → 1.
user: Genos needs your help. He was asked to solve the following programming problem by Saitama:

The length of some string s is denoted |s|. The Hamming distance between two strings s and t of equal length is defined as $\sum_{i = 1}^{|s|}|s_{i} - t_{i}|$, where s_{i} is the i-th character of s and t_{i} is the i-th character of t. For example, the Hamming distance between string "0011" and string "0110" is |0 - 0| + |0 - 1| + |1 - 1| + |1 - 0| = 0 + 1 + 0 + 1 = 2.

Given two binary strings a and b, find the sum of the Hamming distances between a and all contiguous substrings of b of length |a|.


-----Input-----

The first line of the input contains binary string a (1 ≤ |a| ≤ 200 000).

The second line of the input contains binary string b (|a| ≤ |b| ≤ 200 000).

Both strings are guaranteed to consist of characters '0' and '1' only.


-----Output-----

Print a single integer — the sum of Hamming distances between a and all contiguous substrings of b of length |a|.


-----Examples-----
Input
01
00111

Output
3

Input
0011
0110

Output
2



-----Note-----

For the first sample case, there are four contiguous substrings of b of length |a|: "00", "01", "11", and "11". The distance between "01" and "00" is |0 - 0| + |1 - 0| = 1. The distance between "01" and "01" is |0 - 0| + |1 - 1| = 0. The distance between "01" and "11" is |0 - 1| + |1 - 1| = 1. Last distance counts twice, as there are two occurrences of string "11". The sum of these edit distances is 1 + 0 + 1 + 1 = 3.

The second sample case is described in the statement.
user: Let's call an array of non-negative integers $a_1, a_2, \ldots, a_n$ a $k$-extension for some non-negative integer $k$ if for all possible pairs of indices $1 \leq i, j \leq n$ the inequality $k \cdot |i - j| \leq min(a_i, a_j)$ is satisfied. The expansion coefficient of the array $a$ is the maximal integer $k$ such that the array $a$ is a $k$-extension. Any array is a 0-expansion, so the expansion coefficient always exists.

You are given an array of non-negative integers $a_1, a_2, \ldots, a_n$. Find its expansion coefficient.


-----Input-----

The first line contains one positive integer $n$ — the number of elements in the array $a$ ($2 \leq n \leq 300\,000$). The next line contains $n$ non-negative integers $a_1, a_2, \ldots, a_n$, separated by spaces ($0 \leq a_i \leq 10^9$).


-----Output-----

Print one non-negative integer — expansion coefficient of the array $a_1, a_2, \ldots, a_n$.


-----Examples-----
Input
4
6 4 5 5

Output
1
Input
3
0 1 2

Output
0
Input
4
821 500 479 717

Output
239


-----Note-----

In the first test, the expansion coefficient of the array $[6, 4, 5, 5]$ is equal to $1$ because $|i-j| \leq min(a_i, a_j)$, because all elements of the array satisfy $a_i \geq 3$. On the other hand, this array isn't a $2$-extension, because $6 = 2 \cdot |1 - 4| \leq min(a_1, a_4) = 5$ is false.

In the second test, the expansion coefficient of the array $[0, 1, 2]$ is equal to $0$ because this array is not a $1$-extension, but it is $0$-extension.
user: Ivan's classes at the university have just finished, and now he wants to go to the local CFK cafe and eat some fried chicken.

CFK sells chicken chunks in small and large portions. A small portion contains 3 chunks; a large one — 7 chunks. Ivan wants to eat exactly x chunks. Now he wonders whether he can buy exactly this amount of chicken.

Formally, Ivan wants to know if he can choose two non-negative integers a and b in such a way that a small portions and b large ones contain exactly x chunks.

Help Ivan to answer this question for several values of x!


-----Input-----

The first line contains one integer n (1 ≤ n ≤ 100) — the number of testcases.

The i-th of the following n lines contains one integer x_{i} (1 ≤ x_{i} ≤ 100) — the number of chicken chunks Ivan wants to eat.


-----Output-----

Print n lines, in i-th line output YES if Ivan can buy exactly x_{i} chunks. Otherwise, print NO.


-----Example-----
Input
2
6
5

Output
YES
NO



-----Note-----

In the first example Ivan can buy two small portions.

In the second example Ivan cannot buy exactly 5 chunks, since one small portion is not enough, but two small portions or one large is too much.