vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Vasya has n items lying in a line. The items are consecutively numbered by numbers from 1 to n in such a way that the leftmost item has number 1, the rightmost item has number n. Each item has a weight, the i-th item weights w_{i} kilograms.

Vasya needs to collect all these items, however he won't do it by himself. He uses his brand new robot. The robot has two different arms — the left one and the right one. The robot can consecutively perform the following actions:   Take the leftmost item with the left hand and spend w_{i} · l energy units (w_{i} is a weight of the leftmost item, l is some parameter). If the previous action was the same (left-hand), then the robot spends extra Q_{l} energy units;  Take the rightmost item with the right hand and spend w_{j} · r energy units (w_{j} is a weight of the rightmost item, r is some parameter). If the previous action was the same (right-hand), then the robot spends extra Q_{r} energy units; 

Naturally, Vasya wants to program the robot in a way that the robot spends as little energy as possible. He asked you to solve this problem. Your task is to find the minimum number of energy units robot spends to collect all items.


-----Input-----

The first line contains five integers n, l, r, Q_{l}, Q_{r} (1 ≤ n ≤ 10^5; 1 ≤ l, r ≤ 100; 1 ≤ Q_{l}, Q_{r} ≤ 10^4).

The second line contains n integers w_1, w_2, ..., w_{n} (1 ≤ w_{i} ≤ 100).


-----Output-----

In the single line print a single number — the answer to the problem.


-----Examples-----
Input
3 4 4 19 1
42 3 99

Output
576

Input
4 7 2 3 9
1 2 3 4

Output
34



-----Note-----

Consider the first sample. As l = r, we can take an item in turns: first from the left side, then from the right one and last item from the left. In total the robot spends 4·42 + 4·99 + 4·3 = 576 energy units.

The second sample. The optimal solution is to take one item from the right, then one item from the left and two items from the right. In total the robot spends (2·4) + (7·1) + (2·3) + (2·2 + 9) = 34 energy units.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The only difference between easy and hard versions is constraints.

Now elections are held in Berland and you want to win them. More precisely, you want everyone to vote for you.

There are $n$ voters, and two ways to convince each of them to vote for you. The first way to convince the $i$-th voter is to pay him $p_i$ coins. The second way is to make $m_i$ other voters vote for you, and the $i$-th voter will vote for free.

Moreover, the process of such voting takes place in several steps. For example, if there are five voters with $m_1 = 1$, $m_2 = 2$, $m_3 = 2$, $m_4 = 4$, $m_5 = 5$, then you can buy the vote of the fifth voter, and eventually everyone will vote for you. Set of people voting for you will change as follows: ${5} \rightarrow {1, 5} \rightarrow {1, 2, 3, 5} \rightarrow {1, 2, 3, 4, 5}$.

Calculate the minimum number of coins you have to spend so that everyone votes for you.


-----Input-----

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

The first line of each test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of voters.

The next $n$ lines contains the description of voters. $i$-th line contains two integers $m_i$ and $p_i$ ($1 \le p_i \le 10^9, 0 \le m_i < n$).

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


-----Output-----

For each test case print one integer — the minimum number of coins you have to spend so that everyone votes for you.


-----Example-----
Input
3
3
1 5
2 10
2 8
7
0 1
3 1
1 1
6 1
1 1
4 1
4 1
6
2 6
2 3
2 8
2 7
4 4
5 5

Output
8
0
7



-----Note-----

In the first test case you have to buy vote of the third voter. Then the set of people voting for you will change as follows: ${3} \rightarrow {1, 3} \rightarrow {1, 2, 3}$.

In the second example you don't need to buy votes. The set of people voting for you will change as follows: ${1} \rightarrow {1, 3, 5} \rightarrow {1, 2, 3, 5} \rightarrow {1, 2, 3, 5, 6, 7} \rightarrow {1, 2, 3, 4, 5, 6, 7}$.

In the third test case you have to buy votes of the second and the fifth voters. Then the set of people voting for you will change as follows: ${2, 5} \rightarrow {1, 2, 3, 4, 5} \rightarrow {1, 2, 3, 4, 5, 6}$.

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

The great devil Sacagna was still attacked by her natural enemy cat today.
I bought a secret weapon because I couldn't do it all the time.
This secret weapon can block the cat's path of movement by creating huge rocks that keep cats away from you.


Now, Sacagna and one cat are in a rectangular closed section surrounded by trout (0,0), (n−1,0), (n−1, m−1), (0, m−1). I'm in.
There is a cat in the trout (0,0) and Sacagna in the trout (n−1, m−1).
Cats can move to adjacent squares on the top, bottom, left, and right, but cannot go out of the section.
Some squares cannot enter due to the effects of holes and obstacles.
Sacagna can prevent cats from invading a square by creating a rock in that square.
However, rocks cannot be formed on the trout (0,0) and the trout (n−1, m−1).

Find the minimum number of rocks to form needed to block the path of movement from trout (0,0) to trout (n−1, m−1).

Constraints

The input satisfies the following conditions.

* 2 ≤ n, m ≤ 105
* 0 ≤ k ≤ min (n × m−2,105)
* 0 ≤ xi ≤ n − 1
* 0 ≤ yi ≤ m − 1
* (xi, yi) ≠ (xj, yj) (i ≠ j)
* (xi, yi) ≠ (0,0) ≠ (n−1, m−1)

Input


n m k
x1 y1
...
xk yk


All inputs are given as integers.
On the first line, two integers n and m representing the size of the squares and the number k of the squares that cannot be penetrated are given separated by blanks.
From the second line, the coordinates of the cells that cannot enter the k line are given.

Output

Output the minimum number of rocks to be generated in one line, which is necessary to block the movement path from the mass (0,0) to the mass (n−1, m−1).

Examples

Input

3 5 2
0 2
2 2


Output

1


Input

5 5 3
0 2
2 2
4 1


Output

2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Mr. Kitayuta's Colorful Graph

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Mr. Kitayuta has just bought an undirected graph consisting of *n* vertices and *m* edges. The vertices of the graph are numbered from 1 to *n*. Each edge, namely edge *i*, has a color *c**i*, connecting vertex *a**i* and *b**i*.

Mr. Kitayuta wants you to process the following *q* queries.

In the *i*-th query, he gives you two integers — *u**i* and *v**i*.

Find the number of the colors that satisfy the following condition: the edges of that color connect vertex *u**i* and vertex *v**i* directly or indirectly.

Input Specification:
The first line of the input contains space-separated two integers — *n* and *m* (2<=≤<=*n*<=≤<=100,<=1<=≤<=*m*<=≤<=100), denoting the number of the vertices and the number of the edges, respectively.

The next *m* lines contain space-separated three integers — *a**i*, *b**i* (1<=≤<=*a**i*<=&lt;<=*b**i*<=≤<=*n*) and *c**i* (1<=≤<=*c**i*<=≤<=*m*). Note that there can be multiple edges between two vertices. However, there are no multiple edges of the same color between two vertices, that is, if *i*<=≠<=*j*, (*a**i*,<=*b**i*,<=*c**i*)<=≠<=(*a**j*,<=*b**j*,<=*c**j*).

The next line contains a integer — *q* (1<=≤<=*q*<=≤<=100), denoting the number of the queries.

Then follows *q* lines, containing space-separated two integers — *u**i* and *v**i* (1<=≤<=*u**i*,<=*v**i*<=≤<=*n*). It is guaranteed that *u**i*<=≠<=*v**i*.

Output Specification:
For each query, print the answer in a separate line.

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

Demo Output:
['2\n1\n0\n', '1\n1\n1\n1\n2\n']

Note:
Let's consider the first sample. 
 -  Vertex 1 and vertex 2 are connected by color 1 and 2. -  Vertex 3 and vertex 4 are connected by color 3. -  Vertex 1 and vertex 4 are not connected by any single color.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ante and Goran are preparing $N$ teams of young ambitious students for a student programming competition of students from University of Zagreb. Both of them have one algorithm they have to explain to each team. Of course, both can’t work with the same team at the same time and none of them can work with multiple teams simultaneously.

You are given the time it takes for each team to understand and implement an algorithm. Each algorithm lecture has to be done without interruption. Determine the minimal time required for Ante and Goran to do their lectures!

For additional explanation, consult the sample test clarifications.

-----Input-----
The first line of input contains the integer $N$, the number of teams.

The following line contains $N$ space separated integers, where the $i$’th integer denotes the time required for the $i$’th team to understand and implement an algorithm.

All numbers in the input belong to the interval $[1, 3 \cdot 10^5]$.

-----Output-----
The first and only line of output must contain the required number from the task.

Clarification of the first example: Each team needs $2$ units of time to understand and implement an algorithm. One of the possible schedules is that Ante gives his lectures to team $1$, team $2$ and team $3$, respectively, and Goran to team $3$, team $1$ and team $2$, respectively.

Clarification of the second example: One of the optimal schedules is that Ante gives lectures to team $2$, team $3$ and team $1$, respectively, but with a pause lasting $1$ unit of time between team $3$ and team $1$. Goran will give lectures to team $1$, team $3$ and team $2$, respectively.

-----Examples-----
Sample Input 1:
3
2 2 2
Sample Output 1:
6

Sample Input 2:
3
4 1 2
Sample Output 2:
8

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Valya and Tolya are an ideal pair, but they quarrel sometimes. Recently, Valya took offense at her boyfriend because he came to her in t-shirt with lettering that differs from lettering on her pullover. Now she doesn't want to see him and Tolya is seating at his room and crying at her photos all day long.

This story could be very sad but fairy godmother (Tolya's grandmother) decided to help them and restore their relationship. She secretly took Tolya's t-shirt and Valya's pullover and wants to make the letterings on them same. In order to do this, for one unit of mana she can buy a spell that can change some letters on the clothes. Your task is calculate the minimum amount of mana that Tolya's grandmother should spend to rescue love of Tolya and Valya.

More formally, letterings on Tolya's t-shirt and Valya's pullover are two strings with same length *n* consisting only of lowercase English letters. Using one unit of mana, grandmother can buy a spell of form (*c*1,<=*c*2) (where *c*1 and *c*2 are some lowercase English letters), which can arbitrary number of times transform a single letter *c*1 to *c*2 and vise-versa on both Tolya's t-shirt and Valya's pullover. You should find the minimum amount of mana that grandmother should spend to buy a set of spells that can make the letterings equal. In addition you should output the required set of spells.

Input Specification:
The first line contains a single integer *n* (1<=≤<=*n*<=≤<=105) — the length of the letterings.

The second line contains a string with length *n*, consisting of lowercase English letters — the lettering on Valya's pullover.

The third line contains the lettering on Tolya's t-shirt in the same format.

Output Specification:
In the first line output a single integer — the minimum amount of mana *t* required for rescuing love of Valya and Tolya.

In the next *t* lines output pairs of space-separated lowercase English letters — spells that Tolya's grandmother should buy. Spells and letters in spells can be printed in any order.

If there are many optimal answers, output any.

Demo Input:
['3\nabb\ndad\n', '8\ndrpepper\ncocacola\n']

Demo Output:
['2\na d\nb a', '7\nl e\ne d\nd c\nc p\np o\no r\nr a\n']

Note:
In first example it's enough to buy two spells: ('a','d') and ('b','a'). Then first letters will coincide when we will replace letter 'a' with 'd'. Second letters will coincide when we will replace 'b' with 'a'. Third letters will coincide when we will at first replace 'b' with 'a' and then 'a' with 'd'.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Carl is a beginner magician. He has a blue, b violet and c orange magic spheres. In one move he can transform two spheres of the same color into one sphere of any other color. To make a spell that has never been seen before, he needs at least x blue, y violet and z orange spheres. Can he get them (possible, in multiple actions)?


-----Input-----

The first line of the input contains three integers a, b and c (0 ≤ a, b, c ≤ 1 000 000) — the number of blue, violet and orange spheres that are in the magician's disposal.

The second line of the input contains three integers, x, y and z (0 ≤ x, y, z ≤ 1 000 000) — the number of blue, violet and orange spheres that he needs to get.


-----Output-----

If the wizard is able to obtain the required numbers of spheres, print "Yes". Otherwise, print "No".


-----Examples-----
Input
4 4 0
2 1 2

Output
Yes

Input
5 6 1
2 7 2

Output
No

Input
3 3 3
2 2 2

Output
Yes



-----Note-----

In the first sample the wizard has 4 blue and 4 violet spheres. In his first action he can turn two blue spheres into one violet one. After that he will have 2 blue and 5 violet spheres. Then he turns 4 violet spheres into 2 orange spheres and he ends up with 2 blue, 1 violet and 2 orange spheres, which is exactly what he needs.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One day Jeff got hold of an integer sequence a_1, a_2, ..., a_{n} of length n. The boy immediately decided to analyze the sequence. For that, he needs to find all values of x, for which these conditions hold:

  x occurs in sequence a.  Consider all positions of numbers x in the sequence a (such i, that a_{i} = x). These numbers, sorted in the increasing order, must form an arithmetic progression. 

Help Jeff, find all x that meet the problem conditions.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^5). The next line contains integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^5). The numbers are separated by spaces.


-----Output-----

In the first line print integer t — the number of valid x. On each of the next t lines print two integers x and p_{x}, where x is current suitable value, p_{x} is the common difference between numbers in the progression (if x occurs exactly once in the sequence, p_{x} must equal 0). Print the pairs in the order of increasing x.


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

Output
1
2 0

Input
8
1 2 1 3 1 2 1 5

Output
4
1 2
2 4
3 0
5 0



-----Note-----

In the first test 2 occurs exactly once in the sequence, ergo p_2 = 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Akash loves going to school, but not on weekends.  

A week consists of 7 days (Monday to Sunday). Akash takes a leave every Saturday.

If a month consists of N days and the first-day of the month is Monday, find the number of days Akash would take a leave in the whole month.

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

- First line will contain T, the number of test cases. Then the test cases follow.
- Each test case contains a single line of input, one integer N - the number of days in the month.

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

For each test case, output in a single line, the number of days Akash would take a leave in the whole month.

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

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 10^{9}$

------ subtasks ------ 

Subtask 1 (30 points) : $1 ≤ N ≤ 100$
Subtask 2 (70 points) : Original Constraints

----- Sample Input 1 ------ 
4
5
6
8
22
----- Sample Output 1 ------ 
0
1
1
3
----- explanation 1 ------ 
Test case $1$: The month consists of $5$ days (Monday, Tuesday, Wednesday, Thursday, and Friday). Since there are no Saturdays, Akash would go to school every day. Thus, he takes a leave for $0$ days.

Test case $2$: The month consists of $6$ days (Monday, Tuesday, Wednesday, Thursday, Friday, Saturday). Akash takes a leave only on Saturday. Thus, he takes a leave for $1$ day.

Test case $3$: The month consists of $8$ days (Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday, Monday). Akash takes a leave only on Saturday. Thus, he takes a leave for $1$ day.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One department of some software company has $n$ servers of different specifications. Servers are indexed with consecutive integers from $1$ to $n$. Suppose that the specifications of the $j$-th server may be expressed with a single integer number $c_j$ of artificial resource units.

In order for production to work, it is needed to deploy two services $S_1$ and $S_2$ to process incoming requests using the servers of the department. Processing of incoming requests of service $S_i$ takes $x_i$ resource units.

The described situation happens in an advanced company, that is why each service may be deployed using not only one server, but several servers simultaneously. If service $S_i$ is deployed using $k_i$ servers, then the load is divided equally between these servers and each server requires only $x_i / k_i$ (that may be a fractional number) resource units.

Each server may be left unused at all, or be used for deploying exactly one of the services (but not for two of them simultaneously). The service should not use more resources than the server provides.

Determine if it is possible to deploy both services using the given servers, and if yes, determine which servers should be used for deploying each of the services.


-----Input-----

The first line contains three integers $n$, $x_1$, $x_2$ ($2 \leq n \leq 300\,000$, $1 \leq x_1, x_2 \leq 10^9$) — the number of servers that the department may use, and resource units requirements for each of the services.

The second line contains $n$ space-separated integers $c_1, c_2, \ldots, c_n$ ($1 \leq c_i \leq 10^9$) — the number of resource units provided by each of the servers.


-----Output-----

If it is impossible to deploy both services using the given servers, print the only word "No" (without the quotes).

Otherwise print the word "Yes" (without the quotes). 

In the second line print two integers $k_1$ and $k_2$ ($1 \leq k_1, k_2 \leq n$) — the number of servers used for each of the services.

In the third line print $k_1$ integers, the indices of the servers that will be used for the first service.

In the fourth line print $k_2$ integers, the indices of the servers that will be used for the second service.

No index may appear twice among the indices you print in the last two lines. If there are several possible answers, it is allowed to print any of them.


-----Examples-----
Input
6 8 16
3 5 2 9 8 7

Output
Yes
3 2
1 2 6
5 4
Input
4 20 32
21 11 11 12

Output
Yes
1 3
1
2 3 4

Input
4 11 32
5 5 16 16

Output
No

Input
5 12 20
7 8 4 11 9

Output
No



-----Note-----

In the first sample test each of the servers 1, 2 and 6 will will provide $8 / 3 = 2.(6)$ resource units and each of the servers 5, 4 will provide $16 / 2 = 8$ resource units.

In the second sample test the first server will provide $20$ resource units and each of the remaining servers will provide $32 / 3 = 10.(6)$ resource units.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Permutation p is an ordered set of integers p_1,  p_2,  ...,  p_{n}, consisting of n distinct positive integers, each of them doesn't exceed n. We'll denote the i-th element of permutation p as p_{i}. We'll call number n the size or the length of permutation p_1,  p_2,  ...,  p_{n}.

The decreasing coefficient of permutation p_1, p_2, ..., p_{n} is the number of such i (1 ≤ i < n), that p_{i} > p_{i} + 1.

You have numbers n and k. Your task is to print the permutation of length n with decreasing coefficient k.


-----Input-----

The single line contains two space-separated integers: n, k (1 ≤ n ≤ 10^5, 0 ≤ k < n) — the permutation length and the decreasing coefficient.


-----Output-----

In a single line print n space-separated integers: p_1, p_2, ..., p_{n} — the permutation of length n with decreasing coefficient k. 

If there are several permutations that meet this condition, print any of them. It is guaranteed that the permutation with the sought parameters exists.


-----Examples-----
Input
5 2

Output
1 5 2 4 3

Input
3 0

Output
1 2 3

Input
3 2

Output
3 2 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's call an array good if there is an element in the array that equals to the sum of all other elements. For example, the array $a=[1, 3, 3, 7]$ is good because there is the element $a_4=7$ which equals to the sum $1 + 3 + 3$.

You are given an array $a$ consisting of $n$ integers. Your task is to print all indices $j$ of this array such that after removing the $j$-th element from the array it will be good (let's call such indices nice).

For example, if $a=[8, 3, 5, 2]$, the nice indices are $1$ and $4$:   if you remove $a_1$, the array will look like $[3, 5, 2]$ and it is good;  if you remove $a_4$, the array will look like $[8, 3, 5]$ and it is good. 

You have to consider all removals independently, i. e. remove the element, check if the resulting array is good, and return the element into the array.


-----Input-----

The first line of the input contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of elements in the array $a$.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$) — elements of the array $a$.


-----Output-----

In the first line print one integer $k$ — the number of indices $j$ of the array $a$ such that after removing the $j$-th element from the array it will be good (i.e. print the number of the nice indices).

In the second line print $k$ distinct integers $j_1, j_2, \dots, j_k$ in any order — nice indices of the array $a$.

If there are no such indices in the array $a$, just print $0$ in the first line and leave the second line empty or do not print it at all.


-----Examples-----
Input
5
2 5 1 2 2

Output
3
4 1 5
Input
4
8 3 5 2

Output
2
1 4 

Input
5
2 1 2 4 3

Output
0




-----Note-----

In the first example you can remove any element with the value $2$ so the array will look like $[5, 1, 2, 2]$. The sum of this array is $10$ and there is an element equals to the sum of remaining elements ($5 = 1 + 2 + 2$).

In the second example you can remove $8$ so the array will look like $[3, 5, 2]$. The sum of this array is $10$ and there is an element equals to the sum of remaining elements ($5 = 3 + 2$). You can also remove $2$ so the array will look like $[8, 3, 5]$. The sum of this array is $16$ and there is an element equals to the sum of remaining elements ($8 = 3 + 5$).

In the third example you cannot make the given array good by removing exactly one element.

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