vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Bus

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
A bus moves along the coordinate line *Ox* from the point *x*<==<=0 to the point *x*<==<=*a*. After starting from the point *x*<==<=0, it reaches the point *x*<==<=*a*, immediately turns back and then moves to the point *x*<==<=0. After returning to the point *x*<==<=0 it immediately goes back to the point *x*<==<=*a* and so on. Thus, the bus moves from *x*<==<=0 to *x*<==<=*a* and back. Moving from the point *x*<==<=0 to *x*<==<=*a* or from the point *x*<==<=*a* to *x*<==<=0 is called a bus journey. In total, the bus must make *k* journeys.

The petrol tank of the bus can hold *b* liters of gasoline. To pass a single unit of distance the bus needs to spend exactly one liter of gasoline. The bus starts its first journey with a full petrol tank.

There is a gas station in point *x*<==<=*f*. This point is between points *x*<==<=0 and *x*<==<=*a*. There are no other gas stations on the bus route. While passing by a gas station in either direction the bus can stop and completely refuel its tank. Thus, after stopping to refuel the tank will contain *b* liters of gasoline.

What is the minimum number of times the bus needs to refuel at the point *x*<==<=*f* to make *k* journeys? The first journey starts in the point *x*<==<=0.

Input Specification:
The first line contains four integers *a*, *b*, *f*, *k* (0<=&lt;<=*f*<=&lt;<=*a*<=≤<=106, 1<=≤<=*b*<=≤<=109, 1<=≤<=*k*<=≤<=104) — the endpoint of the first bus journey, the capacity of the fuel tank of the bus, the point where the gas station is located, and the required number of journeys.

Output Specification:
Print the minimum number of times the bus needs to refuel to make *k* journeys. If it is impossible for the bus to make *k* journeys, print -1.

Demo Input:
['6 9 2 4\n', '6 10 2 4\n', '6 5 4 3\n']

Demo Output:
['4\n', '2\n', '-1\n']

Note:
In the first example the bus needs to refuel during each journey.

In the second example the bus can pass 10 units of distance without refueling. So the bus makes the whole first journey, passes 4 units of the distance of the second journey and arrives at the point with the gas station. Then it can refuel its tank, finish the second journey and pass 2 units of distance from the third journey. In this case, it will again arrive at the point with the gas station. Further, he can refill the tank up to 10 liters to finish the third journey and ride all the way of the fourth journey. At the end of the journey the tank will be empty. 

In the third example the bus can not make all 3 journeys because if it refuels during the second journey, the tanks will contain only 5 liters of gasoline, but the bus needs to pass 8 units of distance until next refueling.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This problem is same as the previous one, but has larger constraints.

Shiro's just moved to the new house. She wants to invite all friends of her to the house so they can play monopoly. However, her house is too small, so she can only invite one friend at a time.

For each of the $n$ days since the day Shiro moved to the new house, there will be exactly one cat coming to the Shiro's house. The cat coming in the $i$-th day has a ribbon with color $u_i$. Shiro wants to know the largest number $x$, such that if we consider the streak of the first $x$ days, it is possible to remove exactly one day from this streak so that every ribbon color that has appeared among the remaining $x - 1$ will have the same number of occurrences.

For example, consider the following sequence of $u_i$: $[2, 2, 1, 1, 5, 4, 4, 5]$. Then $x = 7$ makes a streak, since if we remove the leftmost $u_i = 5$, each ribbon color will appear exactly twice in the prefix of $x - 1$ days. Note that $x = 8$ doesn't form a streak, since you must remove exactly one day. 

Since Shiro is just a cat, she is not very good at counting and needs your help finding the longest streak.


-----Input-----

The first line contains a single integer $n$ ($1 \leq n \leq 10^5$) — the total number of days.

The second line contains $n$ integers $u_1, u_2, \ldots, u_n$ ($1 \leq u_i \leq 10^5$) — the colors of the ribbons the cats wear. 


-----Output-----

Print a single integer $x$ — the largest possible streak of days.


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

Output
13
Input
5
10 100 20 200 1

Output
5
Input
1
100000

Output
1
Input
7
3 2 1 1 4 5 1

Output
6
Input
6
1 1 1 2 2 2

Output
5


-----Note-----

In the first example, we can choose the longest streak of $13$ days, since upon removing the last day out of the streak, all of the remaining colors $1$, $2$, $3$, and $4$ will have the same number of occurrences of $3$. Note that the streak can also be $10$ days (by removing the $10$-th day from this streak) but we are interested in the longest streak.

In the fourth example, if we take the streak of the first $6$ days, we can remove the third day from this streak then all of the remaining colors $1$, $2$, $3$, $4$ and $5$ will occur exactly once.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Katya studies in a fifth grade. Recently her class studied right triangles and the Pythagorean theorem. It appeared, that there are triples of positive integers such that you can construct a right triangle with segments of lengths corresponding to triple. Such triples are called Pythagorean triples.

For example, triples (3, 4, 5), (5, 12, 13) and (6, 8, 10) are Pythagorean triples.

Here Katya wondered if she can specify the length of some side of right triangle and find any Pythagorean triple corresponding to such length? Note that the side which length is specified can be a cathetus as well as hypotenuse.

Katya had no problems with completing this task. Will you do the same?


-----Input-----

The only line of the input contains single integer n (1 ≤ n ≤ 10^9) — the length of some side of a right triangle.


-----Output-----

Print two integers m and k (1 ≤ m, k ≤ 10^18), such that n, m and k form a Pythagorean triple, in the only line.

In case if there is no any Pythagorean triple containing integer n, print  - 1 in the only line. If there are many answers, print any of them.


-----Examples-----
Input
3

Output
4 5
Input
6

Output
8 10
Input
1

Output
-1
Input
17

Output
144 145
Input
67

Output
2244 2245


-----Note-----[Image]

Illustration for the first sample.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Andrew often reads articles in his favorite magazine 2Char. The main feature of these articles is that each of them uses at most two distinct letters. Andrew decided to send an article to the magazine, but as he hasn't written any article, he just decided to take a random one from magazine 26Char. However, before sending it to the magazine 2Char, he needs to adapt the text to the format of the journal. To do so, he removes some words from the chosen article, in such a way that the remaining text can be written using no more than two distinct letters.

Since the payment depends from the number of non-space characters in the article, Andrew wants to keep the words with the maximum total length.

Input Specification:
The first line of the input contains number *n* (1<=≤<=*n*<=≤<=100) — the number of words in the article chosen by Andrew. Following are *n* lines, each of them contains one word. All the words consist only of small English letters and their total length doesn't exceed 1000. The words are not guaranteed to be distinct, in this case you are allowed to use a word in the article as many times as it appears in the input.

Output Specification:
Print a single integer — the maximum possible total length of words in Andrew's article.

Demo Input:
['4\nabb\ncacc\naaa\nbbb\n', '5\na\na\nbcbcb\ncdecdecdecdecdecde\naaaa\n']

Demo Output:
['9', '6']

Note:
In the first sample the optimal way to choose words is {'abb', 'aaa', 'bbb'}.

In the second sample the word 'cdecdecdecdecdecde' consists of three distinct letters, and thus cannot be used in the article. The optimal answer is {'a', 'a', 'aaaa'}.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The entire world faces the greatest danger as Batman and Superman confront each other. Lex Luthor , inclined to destroy Superman allies with Batman . Batman thinks that Superman has the power to wipe out the entire human race . Luthor gives him a piece of Kryptonite , which can be represented as a string S[] of length M , of only characters ‘a’ and  ‘b’.

Teja ensures Batman that he needs to choose continuous segment of S[] such that it has atleast X number of character ‘a’  and atleast Y number of character ‘b’ . As he is busy to devise the tactics , you need to tell him for Q queries the number of continuous segments between L and R which satisfy the above condition .

Input :-

Given the number of test cases ‘T’ , each test case has the following description.
First line has 3 numbers – M (the length of input string), X (the minimum required frequency of ‘a’ , Y(minimum  required frequency of  ‘b’ in the segment) , and Q(the number of queries).

Second line has the input string S.
Then follows Q lines each having two integers , L and R i.e the lower index and the upper index .

Output :-

For each query of each test case , print number of valid continuous segments between L and R.

Constraints-
1 ≤ T ≤ 100000
1 ≤ X ≤ N ≤ 100000
1 ≤ Y ≤ N ≤ 100000
1 ≤ Q ≤ 100000
1 ≤ L≤ R ≤ 100000

Sum of N over all test cases in one test file does not exceed 100000
Sum of Q over all test cases in one test file does not exceed 100000

Problem Setter:-
Shivam Garg
Problem Tester:-
Teja Vojjala

SAMPLE INPUT
1
7 2 2 3
aabbbaa
2 4
1 6
3 7

SAMPLE OUTPUT
0
4
2

Explanation

The length of given string is 7 , and we need continuous segments having atleast 2 ‘a’ and 2 ‘b’ . 
In the range 2 – 4, “abb” , we have only 1 ‘a’ . So the answer is 0.
In the range 1 – 6 , “aabbba” , we have valid “aabb” ,” aabbb”, “aabbba” ,”abbba” . So answer is 4. 
In the range 3 – 7  , “bbbaa” , we have “bbbaa” ,” bbaa”. So answer is 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's denote a function 

$d(x, y) = \left\{\begin{array}{ll}{y - x,} & {\text{if}|x - y|> 1} \\{0,} & {\text{if}|x - y|\leq 1} \end{array} \right.$

You are given an array a consisting of n integers. You have to calculate the sum of d(a_{i}, a_{j}) over all pairs (i, j) such that 1 ≤ i ≤ j ≤ n.


-----Input-----

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

The second line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9) — elements of the array. 


-----Output-----

Print one integer — the sum of d(a_{i}, a_{j}) over all pairs (i, j) such that 1 ≤ i ≤ j ≤ n.


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

Output
4

Input
4
6 6 5 5

Output
0

Input
4
6 6 4 4

Output
-8



-----Note-----

In the first example:

  d(a_1, a_2) = 0;  d(a_1, a_3) = 2;  d(a_1, a_4) = 0;  d(a_1, a_5) = 2;  d(a_2, a_3) = 0;  d(a_2, a_4) = 0;  d(a_2, a_5) = 0;  d(a_3, a_4) =  - 2;  d(a_3, a_5) = 0;  d(a_4, a_5) = 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Crossing all the hurdles, Gudi now reaches the roof of the castle and she finds Puchi,  the Lord of Azkahar and the Protector of the castle, waiting for her.  After having been through the stages in the castle, Gudi has had a change of heart and no longer wants the treasure. Instead, she expresses her desire to become the Lady of Azkahar. However, the position of the Lady can not be won that easily. Puchi decides to take a final test.
He weaves his magic and  N Islands, spread across a vast sea , appear before them. He goes on the say :   
The Lady needs to rule the masses and take important decisions. Let us see how well can you do that. These are   N  Islands, indexed from 1 to   N. There are   M  bidirectional roads in total, wherein each road connects 2 distinct Islands and multiple roads may connect a pair of Islands. Each of the first   K  Islands i.e.   Islands with index from 1 to   K , have a soldier who  fought valiantly in the battle and wants to get to a shelter.  Each of the last   K  Islands i.e. Island with index from    N  -  K + 1 to   N , have a shelter home that can house only 1 Soldier. 
These soldiers await your commands. The cost effort of reaching a shelter for a soldier is the distance that has to be traveled. In addition, you have the option of using magic to transport the soldiers. One use of magic will allow you to move any solider from any island to any other island. Using your magic once costs  10^4  units of effort. You can always use your magic, but then again it comes at a huge cost. Give a target shelter to each of the soldiers and minimize the overall cost efforts of the scenario.

Help Gudi find the minimum cost efforts.  

Input
First line contains an integer  T. T testcases follow.
Each testcase consists of 3 space-separated integers  N,  M and  K.  M lines follow.
Each of these lines, contains 3 integers  X,  Y and  C, denoting that there is a road between Island  X and Island  Y of distance  C units.  

Output
Print the answer to each testcase in a new line.  

Constraints
 1 ≤ T ≤ 10
 1 ≤ K ≤ 80
 2 K +1 ≤ N ≤ 200
 1 ≤ M ≤ 1000
 1 ≤ X,Y ≤ N
 1 ≤ C ≤ 1000  

SAMPLE INPUT
2
6 8 2
1 2 2
1 6 5
1 4 1
4 3 1
3 6 1
3 5 2
4 5 1
2 6 2
6 5 2
3 1 2
1 4 1
3 5 3
3 6 1
4 3 2

SAMPLE OUTPUT
4
10003

Explanation

For the testcases, Soldiers on Island 1,2 and Shelters on Island 5,6.
In the first testcase, the soldier on Island 1 can travel to Island 5 with cost=2 and the soldier on Island 2 can travel to Island 6 with cost = 2. Hence, total cost=4.
In the second testcase,  the soldier on Island 1 can travel to Island 6 with cost=3 and the soldier on Island 2 has to be transported magically to Island 5 with cost= 10000, thereby total cost= 10003

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Simon loves neatness. So before he goes to bed, Simon wants to complete all chores in the house.

Simon's house looks like a rectangular table consisting of n rows and n columns from above. All rows of the table are numbered from 1 to n from top to bottom. All columns of the table are numbered from 1 to n from left to right. Each cell of the table is a room. Pair (x, y) denotes the room, located at the intersection of the x-th row and the y-th column. For each room we know if the light is on or not there.

Initially Simon is in room (x0, y0). He wants to turn off the lights in all the rooms in the house, and then return to room (x0, y0). Suppose that at the current moment Simon is in the room (x, y). To reach the desired result, he can perform the following steps:

  1. The format of the action is "1". The action is to turn on the light in room (x, y). Simon cannot do it if the room already has light on. 
  2. The format of the action is "2". The action is to turn off the light in room (x, y). Simon cannot do it if the room already has light off. 
  3. The format of the action is "dir" (dir is a character). The action is to move to a side-adjacent room in direction dir. The direction can be left, right, up or down (the corresponding dir is L, R, U or D). Additionally, Simon can move only if he see a light in the direction dir. More formally, if we represent the room, Simon wants to go, as (nx, ny), there shold be an integer k (k > 0), that room (x + (nx - x)k, y + (ny - y)k) has a light. Of course, Simon cannot move out of his house. 



Help Simon, find the sequence of actions that lets him achieve the desired result.

Input

The first line contains three positive integers n, x0, y0 (2 ≤ n ≤ 500, 1 ≤ x0, y0 ≤ n).

Next n lines contain the description of rooms in the house. The i-th line contains n space-separated integers ai1, ai2, ..., ain. If number aij equals zero, then room (i, j) has light off, and if number aij equals one, then room (i, j) has light on. It is guaranteed that at least one room has light on.

Output

If there is no desired sequence of actions, print "NO" (without the quotes). Otherwise, print "YES" (without the quotes) and the description of the required sequence of actions as a string. Note that you do not have to minimize the length of the sequence of actions but you shouldn't use more than 3·106 actions.

Examples

Input

3 1 1
1 0 0
0 1 0
1 0 0


Output

YES
D1R2L2D2UU2


Input

3 1 1
1 0 0
0 1 0
0 0 1


Output

NO

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Johnny drives a truck and must deliver a package from his hometown to the district center. His hometown is located at point 0 on a number line, and the district center is located at the point *d*.

Johnny's truck has a gas tank that holds exactly *n* liters, and his tank is initially full. As he drives, the truck consumes exactly one liter per unit distance traveled. Moreover, there are *m* gas stations located at various points along the way to the district center. The *i*-th station is located at the point *x**i* on the number line and sells an unlimited amount of fuel at a price of *p**i* dollars per liter. Find the minimum cost Johnny must pay for fuel to successfully complete the delivery.

Input Specification:
The first line of input contains three space separated integers *d*, *n*, and *m* (1<=≤<=*n*<=≤<=*d*<=≤<=109, 1<=≤<=*m*<=≤<=200 000) — the total distance to the district center, the volume of the gas tank, and the number of gas stations, respectively.

Each of the next *m* lines contains two integers *x**i*, *p**i* (1<=≤<=*x**i*<=≤<=*d*<=-<=1, 1<=≤<=*p**i*<=≤<=106) — the position and cost of gas at the *i*-th gas station. It is guaranteed that the positions of the gas stations are distinct.

Output Specification:
Print a single integer — the minimum cost to complete the delivery. If there is no way to complete the delivery, print -1.

Demo Input:
['10 4 4\n3 5\n5 8\n6 3\n8 4\n', '16 5 2\n8 2\n5 1\n']

Demo Output:
['22\n', '-1\n']

Note:
In the first sample, Johnny's truck holds 4 liters. He can drive 3 units to the first gas station, buy 2 liters of gas there (bringing the tank to 3 liters total), drive 3 more units to the third gas station, buy 4 liters there to fill up his tank, and then drive straight to the district center. His total cost is 2·5 + 4·3 = 22 dollars.

In the second sample, there is no way for Johnny to make it to the district center, as his tank cannot hold enough gas to take him from the latest gas station to the district center.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
International Women's Day is coming soon! Polycarp is preparing for the holiday.

There are $n$ candy boxes in the shop for sale. The $i$-th box contains $d_i$ candies.

Polycarp wants to prepare the maximum number of gifts for $k$ girls. Each gift will consist of exactly two boxes. The girls should be able to share each gift equally, so the total amount of candies in a gift (in a pair of boxes) should be divisible by $k$. In other words, two boxes $i$ and $j$ ($i \ne j$) can be combined as a gift if $d_i + d_j$ is divisible by $k$.

How many boxes will Polycarp be able to give? Of course, each box can be a part of no more than one gift. Polycarp cannot use boxes "partially" or redistribute candies between them. 


-----Input-----

The first line of the input contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5, 1 \le k \le 100$) — the number the boxes and the number the girls.

The second line of the input contains $n$ integers $d_1, d_2, \dots, d_n$ ($1 \le d_i \le 10^9$), where $d_i$ is the number of candies in the $i$-th box.


-----Output-----

Print one integer — the maximum number of the boxes Polycarp can give as gifts.


-----Examples-----
Input
7 2
1 2 2 3 2 4 10

Output
6

Input
8 2
1 2 2 3 2 4 6 10

Output
8

Input
7 3
1 2 2 3 2 4 5

Output
4



-----Note-----

In the first example Polycarp can give the following pairs of boxes (pairs are presented by indices of corresponding boxes):   $(2, 3)$;  $(5, 6)$;  $(1, 4)$. 

So the answer is $6$.

In the second example Polycarp can give the following pairs of boxes (pairs are presented by indices of corresponding boxes):   $(6, 8)$;  $(2, 3)$;  $(1, 4)$;  $(5, 7)$. 

So the answer is $8$.

In the third example Polycarp can give the following pairs of boxes (pairs are presented by indices of corresponding boxes):   $(1, 2)$;  $(6, 7)$. 

So the answer is $4$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given are an N \times N matrix and an integer K. The entry in the i-th row and j-th column of this matrix is denoted as a_{i, j}. This matrix contains each of 1, 2, \dots, N^2 exactly once.
Sigma can repeat the following two kinds of operation arbitrarily many times in any order.
 - Pick two integers x, y (1 \leq x < y \leq N) that satisfy a_{i, x} + a_{i, y} \leq K for all i (1 \leq i \leq N) and swap the x-th and the y-th columns.
 - Pick two integers x, y (1 \leq x < y \leq N) that satisfy a_{x, i} + a_{y, i} \leq K for all i (1 \leq i \leq N) and swap the x-th and the y-th rows.
How many matrices can he obtain by these operations? Find it modulo 998244353.

-----Constraints-----
 - 1 \leq N \leq 50
 - 1 \leq K \leq 2 \times N^2
 - a_{i, j}'s are a rearrangement of 1, 2, \dots, N^2.
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N K
a_{1, 1} a_{1, 2} ... a_{1, N}
a_{2, 1} a_{2, 2} ... a_{2, N}
:
a_{N, 1} a_{N, 2} ... a_{N, N}

-----Output-----
Print the number of matrices Sigma can obtain modulo 998244353.

-----Sample Input-----
3 13
3 2 7
4 8 9
1 6 5

-----Sample Output-----
12

For example, Sigma can swap two columns, by setting x = 1, y = 2. After that, the resulting matrix will be:
2 3 7
8 4 9
6 1 5

After that, he can swap two row vectors by setting x = 1, y = 3, resulting in the following matrix:
6 1 5
8 4 9
2 3 7


Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's denote the following function f. This function takes an array a of length n and returns an array. Initially the result is an empty array. For each integer i from 1 to n we add element a_i to the end of the resulting array if it is greater than all previous elements (more formally, if a_i > max_{1 ≤ j < i}a_j). Some examples of the function f:

  1. if a = [3, 1, 2, 7, 7, 3, 6, 7, 8] then f(a) = [3, 7, 8]; 
  2. if a = [1] then f(a) = [1]; 
  3. if a = [4, 1, 1, 2, 3] then f(a) = [4]; 
  4. if a = [1, 3, 1, 2, 6, 8, 7, 7, 4, 11, 10] then f(a) = [1, 3, 6, 8, 11]. 



You are given two arrays: array a_1, a_2, ... , a_n and array b_1, b_2, ... , b_m. You can delete some elements of array a (possibly zero). To delete the element a_i, you have to pay p_i coins (the value of p_i can be negative, then you get |p_i| coins, if you delete this element). Calculate the minimum number of coins (possibly negative) you have to spend for fulfilling equality f(a) = b.

Input

The first line contains one integer n (1 ≤ n ≤ 5 ⋅ 10^5) — the length of array a.

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ n) — the array a.

The third line contains n integers p_1, p_2, ..., p_n (|p_i| ≤ 10^9) — the array p.

The fourth line contains one integer m (1 ≤ m ≤ n) — the length of array b.

The fifth line contains m integers b_1, b_2, ..., b_m (1 ≤ b_i ≤ n, b_{i-1} < b_i) — the array b.

Output

If the answer exists, in the first line print YES. In the second line, print the minimum number of coins you have to spend for fulfilling equality f(a) = b.

Otherwise in only line print NO.

Examples

Input


11
4 1 3 3 7 8 7 9 10 7 11
3 5 0 -2 5 3 6 7 8 2 4
3
3 7 10


Output


YES
20


Input


6
2 1 5 3 6 5
3 -9 0 16 22 -14
4
2 3 5 6


Output


NO

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