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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
A group of *n* schoolboys decided to ride bikes. As nobody of them has a bike, the boys need to rent them.

The renting site offered them *m* bikes. The renting price is different for different bikes, renting the *j*-th bike costs *p**j* rubles.

In total, the boys' shared budget is *a* rubles. Besides, each of them has his own personal money, the *i*-th boy has *b**i* personal rubles. The shared budget can be spent on any schoolchildren arbitrarily, but each boy's personal money can be spent on renting only this boy's bike.

Each boy can rent at most one bike, one cannot give his bike to somebody else.

What maximum number of schoolboys will be able to ride bikes? What minimum sum of personal money will they have to spend in total to let as many schoolchildren ride bikes as possible?

Input Specification:
The first line of the input contains three integers *n*, *m* and *a* (1<=≤<=*n*,<=*m*<=≤<=105; 0<=≤<=*a*<=≤<=109). The second line contains the sequence of integers *b*1,<=*b*2,<=...,<=*b**n* (1<=≤<=*b**i*<=≤<=104), where *b**i* is the amount of the *i*-th boy's personal money. The third line contains the sequence of integers *p*1,<=*p*2,<=...,<=*p**m* (1<=≤<=*p**j*<=≤<=109), where *p**j* is the price for renting the *j*-th bike.

Output Specification:
Print two integers *r* and *s*, where *r* is the maximum number of schoolboys that can rent a bike and *s* is the minimum total personal money needed to rent *r* bikes. If the schoolchildren cannot rent any bikes, then *r*<==<=*s*<==<=0.

Demo Input:
['2 2 10\n5 5\n7 6\n', '4 5 2\n8 1 1 2\n6 3 7 5 2\n']

Demo Output:
['2 3\n', '3 8\n']

Note:
In the first sample both schoolchildren can rent a bike. For instance, they can split the shared budget in half (5 rubles each). In this case one of them will have to pay 1 ruble from the personal money and the other one will have to pay 2 rubles from the personal money. In total, they spend 3 rubles of their personal money. This way of distribution of money minimizes the amount of spent personal money.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Tic-Tac-Toe used to be Chef's favourite game during his childhood. Reminiscing in his childhood memories, he decided to create his own "Tic-Tac-Toe", with rules being similar to the original Tic-Tac-Toe, other than the fact that it is played on an NxN board.

The game is played between two players taking turns. First player puts an 'X' in an empty cell of the board, then the second player puts an 'O' in some other free cell. If the first player has K continuous X's or the second player has K continuous O's in row, column or diagonal, then he wins.

Chef started playing this new "Tic-Tac-Toe" with his assistant, beginning as the first player himself (that is, Chef plays 'X's). Currently, the game is ongoign, and it's Chef's turn. However, he needs to leave soon to begin tonight's dinner preparations, and has time to play only one more move. If he can win in one move, output "YES", otherwise output "NO" (without quotes). It is guaranteed that no player has already completed the winning criterion before this turn, and that it's a valid "Tic-Tac-Toe" game.

-----Input-----
The first line of input contains one integer T denoting the number of testcases. First line of each testcase contains two integers N and K, next N lines contains N characters each. Each character is either an 'X' denoting that the first player used this cell, an 'O' meaning that the second player used this cell, or a '.' (a period) representing a free cell.

-----Output-----
For each testcase, output, in a single line, "YES" if Chef can win in one move, or "NO" otherwise.

-----Constraints-----
- 1 ≤ T ≤ 100
- 3 ≤ N ≤ 20
- 1 ≤ K ≤ N

-----Example-----
Input:
3
3 3
XOX
O.O
XOX
3 1
...
...
...
3 2
...
...
...

Output:
YES
YES
NO

Input:
1
4 4
XOXO
OX..
XO..
OXOX

Output:
YES

-----Subtasks-----
- Subtask 1:  K  = 1. Points - 10
- Subtask 2:  N  =  K  = 3. Points - 30
- Subtask 3: Original constraints. Points - 60

-----Explanation-----
Test #1:

In first testcase, put 'X' in (2, 2), in second we can put 'X' in any cell and win. 
Test #2:

If you put an 'X' in (3, 3), there will be four 'X's on the main diagonal (1, 1) - (2, 2) - (3, 3) - (4, 4).

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Alexey recently held a programming contest for students from Berland. *n* students participated in a contest, *i*-th of them solved *a**i* problems. Now he wants to award some contestants. Alexey can award the students with diplomas of three different degrees. Each student either will receive one diploma of some degree, or won't receive any diplomas at all. Let *cnt**x* be the number of students that are awarded with diplomas of degree *x* (1<=≤<=*x*<=≤<=3). The following conditions must hold:
 -  For each *x* (1<=≤<=*x*<=≤<=3) *cnt**x*<=&gt;<=0; -  For any two degrees *x* and *y* *cnt**x*<=≤<=2·*cnt**y*. 
Of course, there are a lot of ways to distribute the diplomas. Let *b**i* be the degree of diploma *i*-th student will receive (or <=-<=1 if *i*-th student won't receive any diplomas). Also for any *x* such that 1<=≤<=*x*<=≤<=3 let *c**x* be the maximum number of problems solved by a student that receives a diploma of degree *x*, and *d**x* be the minimum number of problems solved by a student that receives a diploma of degree *x*. Alexey wants to distribute the diplomas in such a way that:
 1.  If student *i* solved more problems than student *j*, then he has to be awarded not worse than student *j* (it's impossible that student *j* receives a diploma and *i* doesn't receive any, and also it's impossible that both of them receive a diploma, but *b**j*<=&lt;<=*b**i*); 1.  *d*1<=-<=*c*2 is maximum possible; 1.  Among all ways that maximize the previous expression, *d*2<=-<=*c*3 is maximum possible; 1.  Among all ways that correspond to the two previous conditions, *d*3<=-<=*c*<=-<=1 is maximum possible, where *c*<=-<=1 is the maximum number of problems solved by a student that doesn't receive any diploma (or 0 if each student is awarded with some diploma). 
Help Alexey to find a way to award the contestants!

Input Specification:
The first line contains one integer number *n* (3<=≤<=*n*<=≤<=3000).

The second line contains *n* integer numbers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=5000).

Output Specification:
Output *n* numbers. *i*-th number must be equal to the degree of diploma *i*-th contestant will receive (or <=-<=1 if he doesn't receive any diploma).

If there are multiple optimal solutions, print any of them. It is guaranteed that the answer always exists.

Demo Input:
['4\n1 2 3 4\n', '6\n1 4 3 1 1 2\n']

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

Note:
none

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
In Berland each high school student is characterized by academic performance — integer value between 1 and 5.

In high school 0xFF there are two groups of pupils: the group *A* and the group *B*. Each group consists of exactly *n* students. An academic performance of each student is known — integer value between 1 and 5.

The school director wants to redistribute students between groups so that each of the two groups has the same number of students whose academic performance is equal to 1, the same number of students whose academic performance is 2 and so on. In other words, the purpose of the school director is to change the composition of groups, so that for each value of academic performance the numbers of students in both groups are equal.

To achieve this, there is a plan to produce a series of exchanges of students between groups. During the single exchange the director selects one student from the class *A* and one student of class *B*. After that, they both change their groups.

Print the least number of exchanges, in order to achieve the desired equal numbers of students for each academic performance.

Input Specification:
The first line of the input contains integer number *n* (1<=≤<=*n*<=≤<=100) — number of students in both groups.

The second line contains sequence of integer numbers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=5), where *a**i* is academic performance of the *i*-th student of the group *A*.

The third line contains sequence of integer numbers *b*1,<=*b*2,<=...,<=*b**n* (1<=≤<=*b**i*<=≤<=5), where *b**i* is academic performance of the *i*-th student of the group *B*.

Output Specification:
Print the required minimum number of exchanges or -1, if the desired distribution of students can not be obtained.

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

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of integers, you must answer a number of queries. Each query consists of a single integer, $\boldsymbol{x}$, and is performed as follows:

Add $\boldsymbol{x}$ to each element of the array, permanently modifying it for any future queries.
Find the absolute value of each element in the array and print the sum of the absolute values on a new line.

Tip: The Input/Output for this challenge is very large, so you'll have to be creative in your approach to pass all test cases.

Function Description  

Complete the playingWithNumbers function in the editor below.  It should return an array of integers that represent the responses to each query.  

playingWithNumbers has the following parameter(s):  

arr: an array of integers  
queries: an array of integers  

Input Format

The first line contains an integer $n$ the number of elements in $\textbf{arr}$. 

The second line contains $n$ space-separated integers $arr\left[i\right]$. 

The third line contains an integer $\textit{q}$, the number of queries. 

The fourth line contains $\textit{q}$ space-separated integers $\boldsymbol{x}$ where $qumeries[j]=x$.    

Constraints

$1\leq n\leq5\times10^5$  
$1\leq q\leq5\times10^5$  
$-2000\leq arr[i]\leq2000$, where $0\leq i<n$.
$-2000\leq\textit{queries}[j]\leq2000$, where $0\leq j<q$

Output Format

For each query, print the sum of the absolute values of all the array's elements on a new line.

Sample Input
3
-1 2 -3
3
1 -2 3 

Sample Output
5
7
6

Explanation

Query 0: $x=1$ 

Array: $[-1,2,-3]\rightarrow[0,3,-2]$ 

The sum of the absolute values of the updated array's elements is $|0|+|3|+|-2|=0+3+2=5$.    

Query 1: $x=-2$ 

Array: $[0,3,-2]\rightarrow[-2,1,-4]$ 

The sum of the absolute values of the updated array's elements is $|-2|+|1|+|-4|=2+1+4=7$.   

Query 2: $x=3$ 

Array: $[-2,1,-4]\rightarrow[1,4,-1]$ 

The sum of the absolute values of the updated array's elements is $|1|+|4|+|-1|=1+4+1=6$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are playing the following Bulls and Cows game with your friend: You write down a number and ask your friend to guess what the number is. Each time your friend makes a guess, you provide a hint that indicates how many digits in said guess match your secret number exactly in both digit and position (called "bulls") and how many digits match the secret number but locate in the wrong position (called "cows"). Your friend will use successive guesses and hints to eventually derive the secret number.

Write a function to return a hint according to the secret number and friend's guess, use A to indicate the bulls and B to indicate the cows. 

Please note that both secret number and friend's guess may contain duplicate digits.

Example 1:


Input: secret = "1807", guess = "7810"

Output: "1A3B"

Explanation: 1 bull and 3 cows. The bull is 8, the cows are 0, 1 and 7.

Example 2:


Input: secret = "1123", guess = "0111"

Output: "1A1B"

Explanation: The 1st 1 in friend's guess is a bull, the 2nd or 3rd 1 is a cow.

Note: You may assume that the secret number and your friend's guess only contain digits, and their lengths are always equal.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Giga Tower is the tallest and deepest building in Cyberland. There are 17<=777<=777<=777 floors, numbered from <=-<=8<=888<=888<=888 to 8<=888<=888<=888. In particular, there is floor 0 between floor <=-<=1 and floor 1. Every day, thousands of tourists come to this place to enjoy the wonderful view. 

In Cyberland, it is believed that the number "8" is a lucky number (that's why Giga Tower has 8<=888<=888<=888 floors above the ground), and, an integer is lucky, if and only if its decimal notation contains at least one digit "8". For example, 8,<=<=-<=180,<=808 are all lucky while 42,<=<=-<=10 are not. In the Giga Tower, if you write code at a floor with lucky floor number, good luck will always be with you (Well, this round is #278, also lucky, huh?).

Tourist Henry goes to the tower to seek good luck. Now he is at the floor numbered *a*. He wants to find the minimum positive integer *b*, such that, if he walks *b* floors higher, he will arrive at a floor with a lucky number.

Input Specification:
The only line of input contains an integer *a* (<=-<=109<=≤<=*a*<=≤<=109).

Output Specification:
Print the minimum *b* in a line.

Demo Input:
['179\n', '-1\n', '18\n']

Demo Output:
['1\n', '9\n', '10\n']

Note:
For the first sample, he has to arrive at the floor numbered 180.

For the second sample, he will arrive at 8.

Note that *b* should be positive, so the answer for the third sample is 10, not 0.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given an undirected graph consisting of $n$ vertices and $m$ edges. Your task is to find the number of connected components which are cycles.

Here are some definitions of graph theory.

An undirected graph consists of two sets: set of nodes (called vertices) and set of edges. Each edge connects a pair of vertices. All edges are bidirectional (i.e. if a vertex $a$ is connected with a vertex $b$, a vertex $b$ is also connected with a vertex $a$). An edge can't connect vertex with itself, there is at most one edge between a pair of vertices.

Two vertices $u$ and $v$ belong to the same connected component if and only if there is at least one path along edges connecting $u$ and $v$.

A connected component is a cycle if and only if its vertices can be reordered in such a way that:
 -  the first vertex is connected with the second vertex by an edge, -  the second vertex is connected with the third vertex by an edge, -  ... -  the last vertex is connected with the first vertex by an edge, -  all the described edges of a cycle are distinct. 
A cycle doesn't contain any other edges except described above. By definition any cycle contains three or more vertices.

Input Specification:
The first line contains two integer numbers $n$ and $m$ ($1 \le n \le 2 \cdot 10^5$, $0 \le m \le 2 \cdot 10^5$) — number of vertices and edges.

The following $m$ lines contains edges: edge $i$ is given as a pair of vertices $v_i$, $u_i$ ($1 \le v_i, u_i \le n$, $u_i \ne v_i$). There is no multiple edges in the given graph, i.e. for each pair ($v_i, u_i$) there no other pairs ($v_i, u_i$) and ($u_i, v_i$) in the list of edges.

Output Specification:
Print one integer — the number of connected components which are also cycles.

Demo Input:
['5 4\n1 2\n3 4\n5 4\n3 5\n', '17 15\n1 8\n1 12\n5 11\n11 9\n9 15\n15 5\n4 13\n3 13\n4 3\n10 16\n7 10\n16 7\n14 3\n14 4\n17 6\n']

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

Note:
In the first example only component $[3, 4, 5]$ is also a cycle.

The illustration above corresponds to the second example.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Roy and Biv have a set of n points on the infinite number line.

Each point has one of 3 colors: red, green, or blue.

Roy and Biv would like to connect all the points with some edges. Edges can be drawn between any of the two of the given points. The cost of an edge is equal to the distance between the two points it connects.

They want to do this in such a way that they will both see that all the points are connected (either directly or indirectly).

However, there is a catch: Roy cannot see the color red and Biv cannot see the color blue.

Therefore, they have to choose the edges in such a way that if all the red points are removed, the remaining blue and green points are connected (and similarly, if all the blue points are removed, the remaining red and green points are connected).

Help them compute the minimum cost way to choose edges to satisfy the above constraints.


-----Input-----

The first line will contain an integer n (1 ≤ n ≤ 300 000), the number of points.

The next n lines will contain two tokens p_{i} and c_{i} (p_{i} is an integer, 1 ≤ p_{i} ≤ 10^9, c_{i} is a uppercase English letter 'R', 'G' or 'B'), denoting the position of the i-th point and the color of the i-th point. 'R' means red, 'G' denotes green, and 'B' means blue. The positions will be in strictly increasing order.


-----Output-----

Print a single integer, the minimum cost way to solve the problem.


-----Examples-----
Input
4
1 G
5 R
10 B
15 G

Output
23

Input
4
1 G
2 R
3 B
10 G

Output
12



-----Note-----

In the first sample, it is optimal to draw edges between the points (1,2), (1,4), (3,4). These have costs 4, 14, 5, respectively.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The biggest event of the year – Cota 2 world championship "The Innernational" is right around the corner. 2^n teams will compete in a double-elimination format (please, carefully read problem statement even if you know what is it) to identify the champion. 

Teams are numbered from 1 to 2^n and will play games one-on-one. All teams start in the upper bracket.

All upper bracket matches will be held played between teams that haven't lost any games yet. Teams are split into games by team numbers. Game winner advances in the next round of upper bracket, losers drop into the lower bracket.

Lower bracket starts with 2^{n-1} teams that lost the first upper bracket game. Each lower bracket round consists of two games. In the first game of a round 2^k teams play a game with each other (teams are split into games by team numbers). 2^{k-1} loosing teams are eliminated from the championship, 2^{k-1} winning teams are playing 2^{k-1} teams that got eliminated in this round of upper bracket (again, teams are split into games by team numbers). As a result of each round both upper and lower bracket have 2^{k-1} teams remaining. See example notes for better understanding.

Single remaining team of upper bracket plays with single remaining team of lower bracket in grand-finals to identify championship winner.

You are a fan of teams with numbers a_1, a_2, ..., a_k. You want the championship to have as many games with your favourite teams as possible. Luckily, you can affect results of every championship game the way you want. What's maximal possible number of championship games that include teams you're fan of?

Input

First input line has two integers n, k — 2^n teams are competing in the championship. You are a fan of k teams (2 ≤ n ≤ 17; 0 ≤ k ≤ 2^n).

Second input line has k distinct integers a_1, …, a_k — numbers of teams you're a fan of (1 ≤ a_i ≤ 2^n).

Output

Output single integer — maximal possible number of championship games that include teams you're fan of.

Examples

Input


3 1
6


Output


6


Input


3 3
1 7 8


Output


11


Input


3 4
1 3 5 7


Output


14

Note

On the image, each game of the championship is denoted with an English letter (a to n). Winner of game i is denoted as Wi, loser is denoted as Li. Teams you're a fan of are highlighted with red background.

In the first example, team 6 will play in 6 games if it looses the first upper bracket game (game c) and wins all lower bracket games (games h, j, l, m). 

<image>

In the second example, teams 7 and 8 have to play with each other in the first game of upper bracket (game d). Team 8 can win all remaining games in upper bracket, when teams 1 and 7 will compete in the lower bracket. 

<image>

In the third example, your favourite teams can play in all games of the championship. 

<image>

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The last product of the R2 company in the 2D games' field is a new revolutionary algorithm of searching for the shortest path in a 2<=×<=*n* maze.

Imagine a maze that looks like a 2<=×<=*n* rectangle, divided into unit squares. Each unit square is either an empty cell or an obstacle. In one unit of time, a person can move from an empty cell of the maze to any side-adjacent empty cell. The shortest path problem is formulated as follows. Given two free maze cells, you need to determine the minimum time required to go from one cell to the other.

Unfortunately, the developed algorithm works well for only one request for finding the shortest path, in practice such requests occur quite often. You, as the chief R2 programmer, are commissioned to optimize the algorithm to find the shortest path. Write a program that will effectively respond to multiple requests to find the shortest path in a 2<=×<=*n* maze.

Input Specification:
The first line contains two integers, *n* and *m* (1<=≤<=*n*<=≤<=2·105; 1<=≤<=*m*<=≤<=2·105) — the width of the maze and the number of queries, correspondingly. Next two lines contain the maze. Each line contains *n* characters, each character equals either '.' (empty cell), or 'X' (obstacle).

Each of the next *m* lines contains two integers *v**i* and *u**i* (1<=≤<=*v**i*,<=*u**i*<=≤<=2*n*) — the description of the *i*-th request. Numbers *v**i*, *u**i* mean that you need to print the value of the shortest path from the cell of the maze number *v**i* to the cell number *u**i*. We assume that the cells of the first line of the maze are numbered from 1 to *n*, from left to right, and the cells of the second line are numbered from *n*<=+<=1 to 2*n* from left to right. It is guaranteed that both given cells are empty.

Output Specification:
Print *m* lines. In the *i*-th line print the answer to the *i*-th request — either the size of the shortest path or -1, if we can't reach the second cell from the first one.

Demo Input:
['4 7\n.X..\n...X\n5 1\n1 3\n7 7\n1 4\n6 1\n4 7\n5 7\n', '10 3\nX...X..X..\n..X...X..X\n11 7\n7 18\n18 10\n']

Demo Output:
['1\n4\n0\n5\n2\n2\n2\n', '9\n-1\n3\n']

Note:
none

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