vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Oz plays popular MMORPG Dota2. Invoker is one of the favourite Oz's heroes. Oz's skills are not perfect yet, so he uses only two spells - SunStrike and Tornado. Each of these spells takes some mana points to cast and may be used several times. Oz uses the spells to kill neutral creeps in the map. The creeps are placed at line OX, you may assume that each creep is a single point on the line. 
When Oz uses SunStrike, he kills all creeps placed on single point. When Tornado is used then it kills all creeps on a line segment (including creeps placed on the ends of the segment). Oz may cast spells in arbitrary order and may use them at any place of the line, however the length of Tornado segment is fixed. Help Oz to Find, what is the minimum amount of mana points he should spend to kill all the creeps. 

Input :
The first line contains three integers Ms,Mt and Lt - Number of mana points a single SunStrike takes, Number of mana points a single Tornado takes and length of Tornado segment. The second line contains a single integer N - amount of creeps in the line. The next line contains N non-negative integers x1,x2,...,xN - coordinates of creeps on the line.

Output :
Output a single number - minimal amount of mana points necessary to kill all the creeps.

Constraints :
1 ≤ Ms, Mt, Lt ≤ 100 
1 ≤ N ≤ 100 
0 ≤ x1,x2,...,xN ≤ 1000

SAMPLE INPUT
2 3 3
3
1 3 5

SAMPLE OUTPUT
5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given: an array containing hashes of names

Return: a string formatted as a list of names separated by commas except for the last two names, which should be separated by an ampersand.

Example:

``` ruby
list([ {name: 'Bart'}, {name: 'Lisa'}, {name: 'Maggie'} ])
# returns 'Bart, Lisa & Maggie'

list([ {name: 'Bart'}, {name: 'Lisa'} ])
# returns 'Bart & Lisa'

list([ {name: 'Bart'} ])
# returns 'Bart'

list([])
# returns ''
```
``` elixir
list([ %{name: "Bart"}, %{name: "Lisa"}, %{name: "Maggie"} ])
# returns 'Bart, Lisa & Maggie'

list([ %{name: "Bart"}, %{name: "Lisa"} ])
# returns 'Bart & Lisa'

list([ %{name: "Bart"} ])
# returns 'Bart'

list([])
# returns ''
```
``` javascript
list([ {name: 'Bart'}, {name: 'Lisa'}, {name: 'Maggie'} ])
// returns 'Bart, Lisa & Maggie'

list([ {name: 'Bart'}, {name: 'Lisa'} ])
// returns 'Bart & Lisa'

list([ {name: 'Bart'} ])
// returns 'Bart'

list([])
// returns ''
```
```python
namelist([ {'name': 'Bart'}, {'name': 'Lisa'}, {'name': 'Maggie'} ])
# returns 'Bart, Lisa & Maggie'

namelist([ {'name': 'Bart'}, {'name': 'Lisa'} ])
# returns 'Bart & Lisa'

namelist([ {'name': 'Bart'} ])
# returns 'Bart'

namelist([])
# returns ''
```

Note: all the hashes are pre-validated and will only contain A-Z, a-z, '-' and '.'.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya is going to the Olympics in the city Ntown by train. The boy wants to read the textbook to prepare for the Olympics. He counted that he needed k hours for this. He also found that the light in the train changes every hour. The light is measured on a scale from 0 to 100, where 0 is very dark, and 100 is very light.

Vasya has a train lighting schedule for all n hours of the trip — n numbers from 0 to 100 each (the light level in the first hour, the second hour and so on). During each of those hours he will either read the whole time, or not read at all. He wants to choose k hours to read a book, not necessarily consecutive, so that the minimum level of light among the selected hours were maximum. Vasya is very excited before the upcoming contest, help him choose reading hours.

Input

The first input line contains two integers n and k (1 ≤ n ≤ 1000, 1 ≤ k ≤ n) — the number of hours on the train and the number of hours to read, correspondingly. The second line contains n space-separated integers ai (0 ≤ ai ≤ 100), ai is the light level at the i-th hour.

Output

In the first output line print the minimum light level Vasya will read at. In the second line print k distinct space-separated integers b1, b2, ..., bk, — the indexes of hours Vasya will read at (1 ≤ bi ≤ n). The hours are indexed starting from 1. If there are multiple optimal solutions, print any of them. Print the numbers bi in an arbitrary order.

Examples

Input

5 3
20 10 30 40 10


Output

20
1 3 4 


Input

6 5
90 20 35 40 60 100


Output

35
1 3 4 5 6 

Note

In the first sample Vasya should read at the first hour (light 20), third hour (light 30) and at the fourth hour (light 40). The minimum light Vasya will have to read at is 20.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice and Bob went to a pet store. There are N animals in the store where the i^{th} animal is of type A_{i}.

Alice decides to buy some of these N animals. Bob decides that he will buy all the animals left in the store after Alice has made the purchase.

Find out whether it is possible that Alice and Bob end up with exactly same [multiset] of animals. 

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains an integer N — the number of animals in the store.
- The next line contains N space separated integers, denoting the type of each animal.

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

For each test case, output on a new line, YES, if it is possible that Alice and Bob end up with exactly same multiset of animals and NO otherwise.

You may print each character in uppercase or lowercase. For example, the strings YES, yes, Yes, and yES are considered identical.

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

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 100$
- The sum of $N$ over all test cases won't exceed $2\cdot 10^{5}$.

----- Sample Input 1 ------ 
4
3
4 4 4
4
2 3 3 2
4
1 2 2 3
6
5 5 1 5 1 5

----- Sample Output 1 ------ 
NO
YES
NO
YES

----- explanation 1 ------ 
Test case $1$: There are $4$ possible cases:
- Alice does not buy anything: Bob will buy all the animals and will have $3$ animals of type $4$.
- Alice buys $1$ animal of type $4$: Bob will buy the remaining two animals of type $4$.
- Alice buys $2$ animals of type $4$: Bob will buy the remaining one animal of type $4$.
- Alice buys all $3$ animals of type $4$: Bob will not buy anything.

In no case, both Alice and Bob can have the exactly same multiset of pets.

Test case $2$: If Alice buys animals $1$ and $2$, having types $2$ and $3$ respectively, Bob will buy animals $3$ and $4$, having types $3$ and $2$ respectively. Thus, both Alice and Bob have $1$ animal of type $2$ and $1$ animal of type $3$.

Test case $3$: It can be proven that Alice and Bob cannot have the same multiset of pets in any case.

Test case $4$: If Alice buys animals $1, 2, $ and $5$, having types $5, 5,$ and $1$ respectively, Bob will buy animals $3, 4,$ and $6$, having types $1, 5,$ and $5$ respectively. Thus, both Alice and Bob have $1$ animal of type $1$ and $2$ animals of type $5$.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
While walking down the street Vanya saw a label "Hide&amp;Seek". Because he is a programmer, he used &amp; as a bitwise AND for these two words represented as a integers in base 64 and got new word. Now Vanya thinks of some string *s* and wants to know the number of pairs of words of length |*s*| (length of *s*), such that their bitwise AND is equal to *s*. As this number can be large, output it modulo 109<=+<=7.

To represent the string as a number in numeral system with base 64 Vanya uses the following rules:
 -  digits from '0' to '9' correspond to integers from 0 to 9; -  letters from 'A' to 'Z' correspond to integers from 10 to 35; -  letters from 'a' to 'z' correspond to integers from 36 to 61; -  letter '-' correspond to integer 62; -  letter '_' correspond to integer 63.

Input Specification:
The only line of the input contains a single word *s* (1<=≤<=|*s*|<=≤<=100<=000), consisting of digits, lowercase and uppercase English letters, characters '-' and '_'.

Output Specification:
Print a single integer — the number of possible pairs of words, such that their bitwise AND is equal to string *s* modulo 109<=+<=7.

Demo Input:
['z\n', 'V_V\n', 'Codeforces\n']

Demo Output:
['3\n', '9\n', '130653412\n']

Note:
For a detailed definition of bitwise AND we recommend to take a look in the corresponding article in Wikipedia.

In the first sample, there are 3 possible solutions: 
 1.  *z*&amp;_ = 61&amp;63 = 61 = *z* 1.  _&amp;*z* = 63&amp;61 = 61 = *z* 1.  *z*&amp;*z* = 61&amp;61 = 61 = *z*

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
George decided to prepare a Codesecrof round, so he has prepared m problems for the round. Let's number the problems with integers 1 through m. George estimates the i-th problem's complexity by integer b_{i}.

To make the round good, he needs to put at least n problems there. Besides, he needs to have at least one problem with complexity exactly a_1, at least one with complexity exactly a_2, ..., and at least one with complexity exactly a_{n}. Of course, the round can also have problems with other complexities.

George has a poor imagination. It's easier for him to make some already prepared problem simpler than to come up with a new one and prepare it. George is magnificent at simplifying problems. He can simplify any already prepared problem with complexity c to any positive integer complexity d (c ≥ d), by changing limits on the input data.

However, nothing is so simple. George understood that even if he simplifies some problems, he can run out of problems for a good round. That's why he decided to find out the minimum number of problems he needs to come up with in addition to the m he's prepared in order to make a good round. Note that George can come up with a new problem of any complexity.


-----Input-----

The first line contains two integers n and m (1 ≤ n, m ≤ 3000) — the minimal number of problems in a good round and the number of problems George's prepared. The second line contains space-separated integers a_1, a_2, ..., a_{n} (1 ≤ a_1 < a_2 < ... < a_{n} ≤ 10^6) — the requirements for the complexity of the problems in a good round. The third line contains space-separated integers b_1, b_2, ..., b_{m} (1 ≤ b_1 ≤ b_2... ≤ b_{m} ≤ 10^6) — the complexities of the problems prepared by George. 


-----Output-----

Print a single integer — the answer to the problem.


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

Output
0

Input
3 5
1 2 3
1 1 1 1 1

Output
2

Input
3 1
2 3 4
1

Output
3



-----Note-----

In the first sample the set of the prepared problems meets the requirements for a good round.

In the second sample, it is enough to come up with and prepare two problems with complexities 2 and 3 to get a good round.

In the third sample it is very easy to get a good round if come up with and prepare extra problems with complexities: 2, 3, 4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef loves arrays. But he really loves a specific kind of them - Rainbow Arrays. 
The array is a Rainbow Array if it has such a structure:
- The first a1 elements equal to 1. 
- The next a2 elements equal to  2. 
- The next a3 elements equal to  3. 
- The next a4 elements equal to  4. 
- The next a5 elements equal to  5. 
- The next a6 elements equal to  6. 
- The next a7 elements equal to  7. 
- The next a6 elements equal to  6. 
- The next a5 elements equal to  5. 
- The next a4 elements equal to  4. 
- The next a3 elements equal to  3. 
- The next a2 elements equal to  2. 
- The next a1 elements equal to  1. 
- ai is a positive integer, the variables with the same index (a1 in the first statement and a1 in the last one, for example) are equal. 
- There are no any other elements in array. 

For example, {1,1,2,2,2,3,4,5,5,6,7,7,7,6,5,5,4,3,2,2,2,1,1} is a Rainbow Array.

The array {1,2,3,4,5,6,7,6,6,5,4,3,2,1} is not a Rainbow Array, because the sizes of the blocks with the element 6 are different. 
Please help Chef to count the number of different Rainbow Arrays that contain exactly N elements. 

-----Input-----
The first line contains a single integer N. 

-----Output-----
Output the number of different Rainbow Arrays with N elements, modulo 10^9+7. 

-----Constraints-----
- 1 ≤ N ≤ 106

-----Example-----
Input #1:
10 

Output #1:
0

Input #2:
13

Output #2:
1

Input #3:
14

Output #3:
1

Input #4:
15

Output #4:
7

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a program to find the factorial value of any number entered by the user.

-----Input-----

The first line contains an integer T, the total number of testcases. Then T lines follow, each line contains an integer N. 

-----Output-----
For each test case, display the factorial of the given number N in a new line.

-----Constraints-----
- 1 ≤ T ≤ 1000
- 0 ≤ N ≤ 20

-----Example-----
Input
3 
3 
4
5

Output

6
24
120

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Tree is a connected undirected graph that has no cycles. Edge cactus is a connected undirected graph without loops and parallel edges, such that each edge belongs to at most one cycle.

Vasya has an edge cactus, each edge of this graph has some color.

Vasya would like to remove the minimal number of edges in such way that his cactus turned to a tree. Vasya wants to make it in such a way that there were edges of as many different colors in the resulting tree, as possible. Help him to find how many different colors can the resulting tree have.

Input Specification:
The first line contains two integers: *n*, *m* (2<=≤<=*n*<=≤<=10<=000) — the number of vertices and the number of edges in Vasya's graph, respectively.

The following *m* lines contain three integers each: *u*, *v*, *c* (1<=≤<=*u*,<=*v*<=≤<=*n*, *u*<=≠<=*v*, 1<=≤<=*c*<=≤<=*m*) — the numbers of vertices connected by the corresponding edge, and its color. It is guaranteed that the described graph is indeed an edge cactus.

Output Specification:
Output one integer: the maximal number of different colors that the resulting tree can have.

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

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In Croatia there are $N$ cities connected by $E$ two-way roads. Two large food chains have recently reached an agreement on market sharing. In the middle of each road, exactly one chain will be given rights to build a restaurant.

To ensure the market is shared fairly, each city must have at least one restaurant from each chain on the roads connected to that city. However, there are cities with only one road, or no roads at all, and for those cities the above requirement does not apply. Such cities are doomed to visit one chain, or travel a bit further.

Write a program that will determine for each road the chain that should build there so that these requirements are met.

-----Input-----
The first line of input contains two integers $N$ and $E$ ($1 \le N, E \le 100000$), number of cities and number of roads.

The next $E$ lines contain two integers each. Each line describes one road. Integers $A_ i$ and $B_ i$ ($1 \le A_ i , B_ i \le N$; $A_ i \ne B_ i$) denote a road connecting cities $A i$ and $B_ i$.

There will never be two or more roads connecting the same pair of cities.

-----Output-----
If there is no way to fairly assign the roads, the first and only line of input should contain “0”.

Otherwise output exactly $E$ lines, one for each road, in the same order as they were given in the input. The $i^\text {th}$ line should contain “1” if the first chain has the right to build on this road, or “2” if the second one does.

Note: if the solution is not unique, you may output any valid solution.

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

Sample Input 2:
7 7
1 2
2 3
3 1
4 5
5 6
6 7
7 4
Sample Output 2:
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a grid with N rows and N columns of squares. Let (i, j) be the square at the i-th row from the top and the j-th column from the left.

Each of the central (N-2) \times (N-2) squares in the grid has a black stone on it. Each of the 2N - 1 squares on the bottom side and the right side has a white stone on it.

Q queries are given. We ask you to process them in order. There are two kinds of queries. Their input format and description are as follows:

* `1 x`: Place a white stone on (1, x). After that, for each black stone between (1, x) and the first white stone you hit if you go down from (1, x), replace it with a white stone.
* `2 x`: Place a white stone on (x, 1). After that, for each black stone between (x, 1) and the first white stone you hit if you go right from (x, 1), replace it with a white stone.



How many black stones are there on the grid after processing all Q queries?

Constraints

* 3 \leq N \leq 2\times 10^5
* 0 \leq Q \leq \min(2N-4,2\times 10^5)
* 2 \leq x \leq N-1
* Queries are pairwise distinct.

Input

Input is given from Standard Input in the following format:


N Q
Query_1
\vdots
Query_Q


Output

Print how many black stones there are on the grid after processing all Q queries.

Examples

Input

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


Output

1


Input

200000 0


Output

39999200004


Input

176527 15
1 81279
2 22308
2 133061
1 80744
2 44603
1 170938
2 139754
2 15220
1 172794
1 159290
2 156968
1 56426
2 77429
1 97459
2 71282


Output

31159505795

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We are given an array A of N lowercase letter strings, all of the same length.
Now, we may choose any set of deletion indices, and for each string, we delete all the characters in those indices.
For example, if we have an array A = ["abcdef","uvwxyz"] and deletion indices {0, 2, 3}, then the final array after deletions is ["bef", "vyz"], and the remaining columns of A are ["b","v"], ["e","y"], and ["f","z"].  (Formally, the c-th column is [A[0][c], A[1][c], ..., A[A.length-1][c]]).
Suppose we chose a set of deletion indices D such that after deletions, each remaining column in A is in non-decreasing sorted order.
Return the minimum possible value of D.length.
 
Example 1:
Input: A = ["cba","daf","ghi"]
Output: 1
Explanation: 
After choosing D = {1}, each column ["c","d","g"] and ["a","f","i"] are in non-decreasing sorted order.
If we chose D = {}, then a column ["b","a","h"] would not be in non-decreasing sorted order.

Example 2:
Input: A = ["a","b"]
Output: 0
Explanation: D = {}

Example 3:
Input: A = ["zyx","wvu","tsr"]
Output: 3
Explanation: D = {0, 1, 2}

 
Constraints:

1 <= A.length <= 100
1 <= A[i].length <= 1000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your start-up's BA has told marketing that your website has a large audience in Scandinavia and surrounding countries. Marketing thinks it would be great to welcome visitors to the site in their own language. Luckily you already use an API that detects the user's location, so this is an easy win. 

### The Task
- Think of a way to store the languages as a database (eg an object). The languages are listed below so you can copy and paste!
- Write a 'welcome' function that takes a parameter 'language' (always a string), and returns a greeting - if you have it in your database. It should default to English if the language is not in the database, or in the event of an invalid input.

### The Database

```python
'english': 'Welcome',
'czech': 'Vitejte',
'danish': 'Velkomst',
'dutch': 'Welkom',
'estonian': 'Tere tulemast',
'finnish': 'Tervetuloa',
'flemish': 'Welgekomen',
'french': 'Bienvenue',
'german': 'Willkommen',
'irish': 'Failte',
'italian': 'Benvenuto',
'latvian': 'Gaidits',
'lithuanian': 'Laukiamas',
'polish': 'Witamy',
'spanish': 'Bienvenido',
'swedish': 'Valkommen',
'welsh': 'Croeso'
```
``` java
english: "Welcome",
czech: "Vitejte",
danish: "Velkomst",
dutch: "Welkom",
estonian: "Tere tulemast",
finnish: "Tervetuloa",
flemish: "Welgekomen",
french: "Bienvenue",
german: "Willkommen",
irish: "Failte",
italian: "Benvenuto",
latvian: "Gaidits",
lithuanian: "Laukiamas",
polish: "Witamy",
spanish: "Bienvenido",
swedish: "Valkommen",
welsh: "Croeso"
```

Possible invalid inputs include:
~~~~
IP_ADDRESS_INVALID - not a valid ipv4 or ipv6 ip address
IP_ADDRESS_NOT_FOUND - ip address not in the database
IP_ADDRESS_REQUIRED - no ip address was supplied
~~~~

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef is going to start playing Fantasy Football League (FFL) this season. In FFL, each team consists of exactly $15$ players: $2$ goalkeepers, $5$ defenders, $5$ midfielders and $3$ forwards. Chef has already bought $13$ players; he is only missing one defender and one forward.
There are $N$ available players (numbered $1$ through $N$). For each valid $i$, the $i$-th player is either a defender or a forward and has a price $P_i$. The sum of prices of all players in a team must not exceed $100$ dollars and the players Chef bought already cost him $S$ dollars.
Can you help Chef determine if he can complete the team by buying one defender and one forward in such a way that he does not exceed the total price limit?

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains two space-separated integers $N$ and $S$.
- The second line contains $N$ space-separated integers $P_1, P_2, \ldots, P_N$.
- The last line contains $N$ space-separated integers. For each valid $i$, the $i$-th of these integers is $0$ if the $i$-th player is a defender or $1$ if the $i$-th player is a forward.

-----Output-----
For each test case, print a single line containing the string "yes" if it is possible to build a complete team or "no" otherwise (without quotes).

-----Constraints-----
- $1 \le T \le 100$
- $1 \le N \le 100$
- $13 \le S \le 100$
- $1 \le P_i \le 100$ for each valid $i$

-----Subtasks-----
Subtask #1 (100 points): original constraints

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

-----Example Output-----
yes
no

-----Explanation-----
Example case 1: If Chef buys the $1$-st and $3$-rd player, the total price of his team is $90 + 9 = 99$, which is perfectly fine. There is no other valid way to pick two players.
Example case 2: Chef cannot buy two players in such a way that all conditions are satisfied.

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