vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Write a program which reads a sequence of integers $A = \\{a_0, a_1, ..., a_{n-1}\\}$ and reverse specified elements by a list of the following operation:

* reverse($b, e$): reverse the order of $a_b, a_{b+1}, ..., a_{e-1}$

Constraints

* $1 \leq n \leq 1,000$
* $-1,000,000,000 \leq a_i \leq 1,000,000,000$
* $1 \leq q \leq 1,000$
* $0 \leq b < e \leq n$

Input

The input is given in the following format.


$n$
$a_0 \; a_1 \; ...,\; a_{n-1}$
$q$
$b_1 \; e_1$
$b_2 \; e_2$
:
$b_{q} \; b_{q}$


In the first line, $n$ (the number of elements in $A$) is given. In the second line, $a_i$ (each element in $A$) are given. In the third line, the number of queries $q$ is given and each query is given by two integers $b_i \; e_i$ in the following $q$ lines.

Output

Print all elements of $A$ in a line after performing the given operations. Put a single space character between adjacency elements and a newline at the end of the last element.

Example

Input

8
1 2 3 4 5 6 7 8
2
1 6
3 8


Output

1 6 5 8 7 2 3 4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Many internet protocols these days include the option of associating a
media type with the content being sent.
The type is usually inferred from the file extension.
You are to write a program that facilitates the lookup of media types for
a number of files.
You will be given a table of media type associations that associate a certain
file extension with a certain media type.
You will then be given a number of file names, and tasked to determine the correct
media type for each file.
A file extension is defined as the part of the file name after the final period.
If a file name has no periods, then it has no extension and the media type cannot
be determined.
If the file extension is not present in the table, then the media type cannot be
determined.
In such cases you will print "unknown" as the media type.
If the file extension does appear in the table (case matters), then print the associated
media type.

-----Input-----
Input begins with 2 integers N and Q on a line.
N is the number of media type associations, and Q is the number of file names.
Following this are N lines, each containing a file extension and a media type, separated by a space.
Finally, Q lines, each containing the name of a file.
N and Q will be no greater than 100 each.
File extensions will consist only of alphanumeric characters, will have length at most 10, and will be distinct.
Media types will have length at most 50, and will contain only alphanumeric characters and punctuation.
File names will consist only of alphanumeric characters and periods and have length at most 50.

-----Output-----
For each of the Q file names, print on a line the media type of the file.
If there is no matching entry, print "unknown" (quotes for clarity).

-----Sample Input-----
5 6
html text/html
htm text/html
png image/png
svg image/svg+xml
txt text/plain
index.html
this.file.has.lots.of.dots.txt
nodotsatall
virus.exe
dont.let.the.png.fool.you
case.matters.TXT

-----Sample Output-----
text/html
text/plain
unknown
unknown
unknown
unknown

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Since entering $2^\text {nd}$ grade Theta has daily math homework sheets. The problems on her worksheet usually go like this: There is a certain number of birds, dogs, and cats on a farm. Together they have $14$ legs. How many birds, dogs, and cats could there be? Write down as many answers as you can! 

It is always the same problem, just written in different ways: sometimes with horses, cows, sheep, goats, chickens, beetles, or even spiders – but never with snakes or fishes!

Can you write a program to double-check Theta’s answers?

-----Input-----
Input consists of a single line with $4$ integers: $b$, $d$, $c$, and $l$, with $b$, $d$, and $c$ representing the numbers of legs the first, second, and third type of animal has. You are given that $0 < b, c, d \le 100$ because some farm animals in these math problems may be centipedes. The total number of legs is given by $l$ ($0 \le l \le 250$).

-----Output-----
Output all possible answers, each on a separate line, in lexicographical order so that they are sorted by the number of the first animal, ties broken by the second and third animal numbers’, respectively. Separate the number of the first, second, and third animal with spaces. If there are no possible solutions, output impossible on a single line!

-----Examples-----
Sample Input 1:
2 4 4 14
Sample Output 1:
1 0 3
1 1 2
1 2 1
1 3 0
3 0 2
3 1 1
3 2 0
5 0 1
5 1 0
7 0 0

Sample Input 2:
100 80 60 240
Sample Output 2:
0 0 4
0 3 0
1 1 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Employees of JebTrains are on their way to celebrate the 256-th day of the year! There are n employees and k teams in JebTrains. Each employee is a member of some (exactly one) team. All teams are numbered from 1 to k. You are given an array of numbers t_1, t_2, ..., t_n where t_i is the i-th employee's team number.

JebTrains is going to rent a single bus to get employees to the feast. The bus will take one or more rides. A bus can pick up an entire team or two entire teams. If three or more teams take a ride together they may start a new project which is considered unacceptable. It's prohibited to split a team, so all members of a team should take the same ride.

It is possible to rent a bus of any capacity s. Such a bus can take up to s people on a single ride. The total cost of the rent is equal to s ⋅ r burles where r is the number of rides. Note that it's impossible to rent two or more buses.

Help JebTrains to calculate the minimum cost of the rent, required to get all employees to the feast, fulfilling all the conditions above.

Input

The first line contains two integers n and k (1 ≤ n ≤ 5⋅10^5, 1 ≤ k ≤ 8000) — the number of employees and the number of teams in JebTrains. The second line contains a sequence of integers t_1, t_2, ..., t_n, where t_i (1 ≤ t_i ≤ k) is the i-th employee's team number. Every team contains at least one employee.

Output

Print the minimum cost of the rent.

Examples

Input


6 3
3 1 2 3 2 3


Output


6


Input


10 1
1 1 1 1 1 1 1 1 1 1


Output


10


Input


12 4
1 2 3 1 2 3 4 1 2 1 2 1


Output


12

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an undirected connected graph consisting of n vertices and m edges. There are no loops and no multiple edges in the graph.

You are also given two distinct vertices s and t, and two values ds and dt. Your task is to build any spanning tree of the given graph (note that the graph is not weighted), such that the degree of the vertex s doesn't exceed ds, and the degree of the vertex t doesn't exceed dt, or determine, that there is no such spanning tree.

The spanning tree of the graph G is a subgraph which is a tree and contains all vertices of the graph G. In other words, it is a connected graph which contains n - 1 edges and can be obtained by removing some of the edges from G.

The degree of a vertex is the number of edges incident to this vertex.

Input

The first line of the input contains two integers n and m (2 ≤ n ≤ 200 000, 1 ≤ m ≤ min(400 000, n·(n - 1) / 2)) — the number of vertices and the number of edges in the graph. 

The next m lines contain the descriptions of the graph's edges. Each of the lines contains two integers u and v (1 ≤ u, v ≤ n, u ≠ v) — the ends of the corresponding edge. It is guaranteed that the graph contains no loops and no multiple edges and that it is connected.

The last line contains four integers s, t, ds, dt (1 ≤ s, t ≤ n, s ≠ t, 1 ≤ ds, dt ≤ n - 1).

Output

If the answer doesn't exist print "No" (without quotes) in the only line of the output. 

Otherwise, in the first line print "Yes" (without quotes). In the each of the next (n - 1) lines print two integers — the description of the edges of the spanning tree. Each of the edges of the spanning tree must be printed exactly once.

You can output edges in any order. You can output the ends of each edge in any order.

If there are several solutions, print any of them.

Examples

Input

3 3
1 2
2 3
3 1
1 2 1 1


Output

Yes
3 2
1 3


Input

7 8
7 4
1 3
5 4
5 7
3 2
2 4
6 1
1 2
6 4 1 4


Output

Yes
1 3
5 7
3 2
7 4
2 4
6 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each the array element between two given indices, inclusive.  Once all operations have been performed, return the maximum value in the array.  

Example 

$n=10$ 

$queries=[[1,5,3],[4,8,7],[6,9,1]$  

Queries are interpreted as follows:  

    a b k
    1 5 3
    4 8 7
    6 9 1

Add the values of $\boldsymbol{\mbox{k}}$ between the indices $\class{ML__boldsymbol}{\boldsymbol{a}}$ and $\boldsymbol{b}$ inclusive:

index->	 1 2 3  4  5 6 7 8 9 10
	[0,0,0, 0, 0,0,0,0,0, 0]
	[3,3,3, 3, 3,0,0,0,0, 0]
	[3,3,3,10,10,7,7,7,0, 0]
	[3,3,3,10,10,8,8,8,1, 0]

The largest value is $10$ after all operations are performed.  

Function Description  

Complete the function arrayManipulation in the editor below.  

arrayManipulation has the following parameters:

int n - the number of elements in the array  
int queries[q][3] - a two dimensional array of queries where each queries[i] contains three integers, a, b, and k.  

Returns  

int - the maximum value in the resultant array  

Input Format

The first line contains two space-separated integers $n$ and $m$, the size of the array and the number of operations. 

Each of the next $m$ lines contains three space-separated integers $\class{ML__boldsymbol}{\boldsymbol{a}}$, $\boldsymbol{b}$ and $\boldsymbol{\mbox{k}}$, the left index, right index and summand.  

Constraints

$3\leq n\leq10^7$  
$1\leq m\leq2*10^5$  
$1\leq a\leq b\leq n$  
$0\leq k\leq10^9$  

Sample Input
5 3
1 2 100
2 5 100
3 4 100

Sample Output
200

Explanation

After the first update the list is 100 100 0 0 0. 

After the second update list is 100 200 100 100 100. 

After the third update list is 100 200 200 200 100.  

The maximum value is $\textbf{200}$.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
String diversity is the number of symbols that occur in the string at least once. Diversity of *s* will be denoted by *d*(*s*). For example , *d*("aaa")=1, *d*("abacaba")=3.

Given a string *s*, consisting of lowercase Latin letters. Consider all its substrings. Obviously, any substring diversity is a number from 1 to *d*(*s*). Find statistics about substrings diversity: for each *k* from 1 to *d*(*s*), find how many substrings of *s* has a diversity of exactly *k*.

Input Specification:
The input consists of a single line containing *s*. It contains only lowercase Latin letters, the length of *s* is from 1 to 3·105.

Output Specification:
Print to the first line the value *d*(*s*). Print sequence *t*1,<=*t*2,<=...,<=*t**d*(*s*) to the following lines, where *t**i* is the number of substrings of *s* having diversity of exactly *i*.

Demo Input:
['abca\n', 'aabacaabbad\n']

Demo Output:
['3\n4\n3\n3\n', '4\n14\n19\n28\n5\n']

Note:
Consider the first example.

We denote by *s*(*i*, *j*) a substring of "abca" with the indices in the segment [*i*, *j*].
 -  *s*(1, 1) =  "a", *d*("a") = 1 -  *s*(2, 2) =  "b", *d*("b") = 1 -  *s*(3, 3) =  "c", *d*("c") = 1 -  *s*(4, 4) =  "a", *d*("a") = 1 -  *s*(1, 2) =  "ab", *d*("ab") = 2 -  *s*(2, 3) =  "bc", *d*("bc") = 2 -  *s*(3, 4) =  "ca", *d*("ca") = 2 -  *s*(1, 3) =  "abc", *d*("abc") = 3 -  *s*(2, 4) =  "bca", *d*("bca") = 3 -  *s*(1, 4) =  "abca", *d*("abca") = 3 
Total number of substring with diversity 1 is 4, with diversity 2 equals 3, 3 diversity is 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Everybody knows the classic ["half your age plus seven"](https://en.wikipedia.org/wiki/Age_disparity_in_sexual_relationships#The_.22half-your-age-plus-seven.22_rule) dating rule that a lot of people follow (including myself). It's the 'recommended' age range in which to date someone. 




```minimum age <= your age <= maximum age```
#Task

Given an integer (1 <= n <= 100) representing a person's age, return their minimum and maximum age range.

This equation doesn't work when the age <= 14, so use this equation instead:
```
min = age - 0.10 * age
max = age + 0.10 * age
```
You should floor all your answers so that an integer is given instead of a float (which doesn't represent age). ```Return your answer in the form [min]-[max]```

##Examples:

```
age = 27   =>   20-40
age = 5    =>   4-5
age = 17   =>   15-20
```

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

Time Limit: 1 seconds

Memory Limit: 64 megabytes

Problem Description:
Peter decided to wish happy birthday to his friend from Australia and send him a card. To make his present more mysterious, he decided to make a chain. Chain here is such a sequence of envelopes *A*<==<={*a*1,<=<=*a*2,<=<=...,<=<=*a**n*}, where the width and the height of the *i*-th envelope is strictly higher than the width and the height of the (*i*<=<=-<=<=1)-th envelope respectively. Chain size is the number of envelopes in the chain. 

Peter wants to make the chain of the maximum size from the envelopes he has, the chain should be such, that he'll be able to put a card into it. The card fits into the chain if its width and height is lower than the width and the height of the smallest envelope in the chain respectively. It's forbidden to turn the card and the envelopes. 

Peter has very many envelopes and very little time, this hard task is entrusted to you.

Input Specification:
The first line contains integers *n*, *w*, *h* (1<=<=≤<=*n*<=≤<=5000, 1<=≤<=*w*,<=<=*h*<=<=≤<=106) — amount of envelopes Peter has, the card width and height respectively. Then there follow *n* lines, each of them contains two integer numbers *w**i* and *h**i* — width and height of the *i*-th envelope (1<=≤<=*w**i*,<=<=*h**i*<=≤<=106).

Output Specification:
In the first line print the maximum chain size. In the second line print the numbers of the envelopes (separated by space), forming the required chain, starting with the number of the smallest envelope. Remember, please, that the card should fit into the smallest envelope. If the chain of maximum size is not unique, print any of the answers.

If the card does not fit into any of the envelopes, print number 0 in the single line.

Demo Input:
['2 1 1\n2 2\n2 2\n', '3 3 3\n5 4\n12 11\n9 8\n']

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You're in ancient Greece and giving Philoctetes a hand in preparing a training exercise for Hercules! You've filled a pit with two different ferocious mythical creatures for Hercules to battle!

The formidable **"Orthus"** is a 2 headed dog with 1 tail.  The mighty **"Hydra"** has 5 heads and 1 tail. 

Before Hercules goes in, he asks you "How many of each beast am  I up against!?".

You know the total number of heads and the total number of tails, that's the dangerous parts, right? But you didn't consider how many of each beast. 

## Task

Given the number of heads and the number of tails, work out the number of each mythical beast! 

The data is given as two parameters. Your answer should be returned as an array:
```python 
 VALID ->      [24 , 15]           INVALID ->  "No solutions"
```

If there aren't any cases for the given amount of heads and tails - return "No solutions" or null (C#).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array arr.  You can choose a set of integers and remove all the occurrences of these integers in the array.
Return the minimum size of the set so that at least half of the integers of the array are removed.
 
Example 1:
Input: arr = [3,3,3,3,5,5,5,2,2,7]
Output: 2
Explanation: Choosing {3,7} will make the new array [5,5,5,2,2] which has size 5 (i.e equal to half of the size of the old array).
Possible sets of size 2 are {3,5},{3,2},{5,2}.
Choosing set {2,7} is not possible as it will make the new array [3,3,3,3,5,5,5] which has size greater than half of the size of the old array.

Example 2:
Input: arr = [7,7,7,7,7,7]
Output: 1
Explanation: The only possible set you can choose is {7}. This will make the new array empty.

Example 3:
Input: arr = [1,9]
Output: 1

Example 4:
Input: arr = [1000,1000,3,7]
Output: 1

Example 5:
Input: arr = [1,2,3,4,5,6,7,8,9,10]
Output: 5

 
Constraints:

1 <= arr.length <= 10^5
arr.length is even.
1 <= arr[i] <= 10^5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Taboo is a popular party game. In this game one player, the Clue Giver, prompts his/her teammates to guess a keyword by giving clues. The Clue Giver is also given a list of taboo strings that must not appear in the clues. For example, if the keyword is “Bruce Lee”, the famous kung-fu star, then the taboo strings may be “actor”, “kung-fu”, “fighting”, “martial arts” and “The Game of Death” (Bruce Lee’s final film). The Clue Giver may try such clues as “Fist of Fury star” and “Jeet Kune Do master” to avoid the taboo. Taboo strings bring challenges and fun to the guessing game.

Short clues are preferred, but now you are interested in the opposite: what is the longest clue? Given $N$ taboo strings $s_1, \dots , s_ N$, what is the longest clue string $s$ such that none of $s_1, \dots , s_ N$ appears as a substring of $s$? For simplicity, all taboo strings and your clue are represented as binary strings consisting only of 0’s and 1’s.

-----Input-----
The first line contains an integer, $N$, the number of taboo strings ($1 \leq N \leq 15000$). The following $N$ lines each contains a non-empty binary string $s_ i$, for $1 \leq i \leq N$. The sum of lengths of $s_1, \dots , s_ N$ will be at most $200000$.

-----Output-----
If your clue can be arbitrarily long, output -1. Otherwise, output a line containing the longest binary string that does not contain $s_1, \dots , s_ N$ as a substring. If there is more than one such longest string, output the one that is also smallest in lexicographic order.

-----Examples-----
Sample Input:
5
00
01
10
110
111
Sample Output:
11

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is BST given with the root node with the key part as an integer only. You need to find the in-order successor and predecessor of a given key. If either predecessor or successor is not found, then set it to NULL.
Note:- In an inorder traversal the number just smaller than the target is the predecessor and the number just greater than the target is the successor. 
Example 1:
Input:
        10
      /   \
     2    11
   /  \ 
  1    5
      /  \
     3    6
      \
       4
key = 8
Output: 
6 10
Explanation: 
In the given BST the inorder predecessor of 8 is 6 and inorder successor of 8 is 10.
Example 2:
Input:
      8
    /   \
   1     9
    \     \
     4    10
    /
   3
key = 11
Output: 
10 -1
Explanation: 
In given BST, the inorder predecessor of 11 is 10 whereas it does not have any inorder successor.
Your Task: You don't need to print anything. You need to update pre with the predecessor of the key or NULL if the predecessor doesn't exist and succ to the successor of the key or NULL if the successor doesn't exist. pre and succ are passed as an argument to the function findPreSuc(). 
Expected Time Complexity: O(Height of the BST).Expected Auxiliary Space: O(Height of the BST).
Constraints: 
1 <= Number of nodes <= 10^{4}
1 <= key of node <= 10^{7}
1 <= key <= 10^{7}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given n boxes, each box is given in the format [status, candies, keys, containedBoxes] where:

status[i]: an integer which is 1 if box[i] is open and 0 if box[i] is closed.
candies[i]: an integer representing the number of candies in box[i].
keys[i]: an array contains the indices of the boxes you can open with the key in box[i].
containedBoxes[i]: an array contains the indices of the boxes found in box[i].

You will start with some boxes given in initialBoxes array. You can take all the candies in any open box and you can use the keys in it to open new boxes and you also can use the boxes you find in it.
Return the maximum number of candies you can get following the rules above.
 
Example 1:
Input: status = [1,0,1,0], candies = [7,5,4,100], keys = [[],[],[1],[]], containedBoxes = [[1,2],[3],[],[]], initialBoxes = [0]
Output: 16
Explanation: You will be initially given box 0. You will find 7 candies in it and boxes 1 and 2. Box 1 is closed and you don't have a key for it so you will open box 2. You will find 4 candies and a key to box 1 in box 2.
In box 1, you will find 5 candies and box 3 but you will not find a key to box 3 so box 3 will remain closed.
Total number of candies collected = 7 + 4 + 5 = 16 candy.

Example 2:
Input: status = [1,0,0,0,0,0], candies = [1,1,1,1,1,1], keys = [[1,2,3,4,5],[],[],[],[],[]], containedBoxes = [[1,2,3,4,5],[],[],[],[],[]], initialBoxes = [0]
Output: 6
Explanation: You have initially box 0. Opening it you can find boxes 1,2,3,4 and 5 and their keys. The total number of candies will be 6.

Example 3:
Input: status = [1,1,1], candies = [100,1,100], keys = [[],[0,2],[]], containedBoxes = [[],[],[]], initialBoxes = [1]
Output: 1

Example 4:
Input: status = [1], candies = [100], keys = [[]], containedBoxes = [[]], initialBoxes = []
Output: 0

Example 5:
Input: status = [1,1,1], candies = [2,3,2], keys = [[],[],[]], containedBoxes = [[],[],[]], initialBoxes = [2,1,0]
Output: 7

 
Constraints:

1 <= status.length <= 1000
status.length == candies.length == keys.length == containedBoxes.length == n
status[i] is 0 or 1.
1 <= candies[i] <= 1000
0 <= keys[i].length <= status.length
0 <= keys[i][j] < status.length
All values in keys[i] are unique.
0 <= containedBoxes[i].length <= status.length
0 <= containedBoxes[i][j] < status.length
All values in containedBoxes[i] are unique.
Each box is contained in one box at most.
0 <= initialBoxes.length <= status.length
0 <= initialBoxes[i] < status.length

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Ilya the Lion wants to help all his friends with passing exams. They need to solve the following problem to pass the IT exam.

You've got string *s*<==<=*s*1*s*2... *s**n* (*n* is the length of the string), consisting only of characters "." and "#" and *m* queries. Each query is described by a pair of integers *l**i*,<=*r**i* (1<=≤<=*l**i*<=&lt;<=*r**i*<=≤<=*n*). The answer to the query *l**i*,<=*r**i* is the number of such integers *i* (*l**i*<=≤<=*i*<=&lt;<=*r**i*), that *s**i*<==<=*s**i*<=+<=1.

Ilya the Lion wants to help his friends but is there anyone to help him? Help Ilya, solve the problem.

Input Specification:
The first line contains string *s* of length *n* (2<=≤<=*n*<=≤<=105). It is guaranteed that the given string only consists of characters "." and "#".

The next line contains integer *m* (1<=≤<=*m*<=≤<=105) — the number of queries. Each of the next *m* lines contains the description of the corresponding query. The *i*-th line contains integers *l**i*,<=*r**i* (1<=≤<=*l**i*<=&lt;<=*r**i*<=≤<=*n*).

Output Specification:
Print *m* integers — the answers to the queries in the order in which they are given in the input.

Demo Input:
['......\n4\n3 4\n2 3\n1 6\n2 6\n', '#..###\n5\n1 3\n5 6\n1 5\n3 6\n3 4\n']

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

Note:
none

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