vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Concatenation of two integers is obtained as follows: First, convert both integers to strings. Then concatenate both strings into one and convert this concatenated string back to integer.

For example, concatenation of 6 and 7 is CONC(6, 7) = 67, concatenation of 123 and 45 is CONC(123, 45) = 12345.

You are given an array A consisting of N integers. You are also given two integers L and R. Find the number of pairs (i, j) such that  1 ≤ i, j ≤ N and   L ≤ CONC(A_{i}, A_{j}) ≤ R

Note: Since the size of the input and output is large, please use fast input-output methods.

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

- The first line will contain T, the number of test cases. Then T test cases follow.
- The first line of each test case contains three integers N, L, R.
- The second line of each test case line contains N integers A_{1}, A_{2},\dots, A_{N}. 

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

For each testcase, output in a single line the number of suitable pairs.

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

$1 ≤ T ≤ 10^{4}$
$1 ≤ N ≤ 10^{5}$
$1 ≤ L ≤ R ≤ 10^{15}$
$1 ≤ A_{i} ≤ 10^{7}$
- Sum of $N$ over all test cases does not exceed $10^{6}$.

----- Sample Input 1 ------ 
4
2 10 52
2 5
3 58 100
4 2 3
4 100 1000
1 10 100 1000
5 28 102
3 2 1 9 10

----- Sample Output 1 ------ 
3
0
2
11

----- explanation 1 ------ 
Test case 1: 

- $(i = 1, j = 1)$: $CONC(A_{1}, A_{1}) = 22$ and $10 ≤ 22 ≤ 52$.

- $(i = 1, j = 2)$: $CONC(A_{1}, A_{2}) = 25$ and $10 ≤ 25 ≤ 52$.

- $(i = 2, j = 1)$: $CONC(A_{2}, A_{1}) = 52$ and $10 ≤ 52 ≤ 52$.

- $(i = 2, j = 2)$: $CONC(A_{2}, A_{2}) = 55$ and $10 ≤ 55$ but $ 55 \nleq 52$.

So there are three suitable pairs.

Test case 2: There is no suitable pair.

Test case 3: The suitable pairs are $(2, 1)$ and $(1, 2)$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of integers and a sum B, find all unique combinations in the array where the sum is equal to B. The same number may be chosen from the array any number of times to make B.
Note:
        1. All numbers will be positive integers.
        2. Elements in a combination (a1, a2, …, ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
        3. The combinations themselves must be sorted in ascending order.
Example 1:
Input:
N = 4
arr[] = {7,2,6,5}
B = 16
Output:
(2 2 2 2 2 2 2 2)
(2 2 2 2 2 6)
(2 2 2 5 5)
(2 2 5 7)
(2 2 6 6)
(2 7 7)
(5 5 6)
Example 2:
Input:
N = 11
arr[] = {6,5,7,1,8,2,9,9,7,7,9}
B = 6
Output:
(1 1 1 1 1 1)
(1 1 1 1 2)
(1 1 2 2)
(1 5)
(2 2 2)
(6)
Your Task:
Your task is to complete the function combinationSum() which takes the array A and a sum B as inputs and returns a list of list denoting the required combinations in the order specified in the problem description. The printing is done by the driver's code. If no set can be formed with the given set, then  "Empty" (without quotes) is printed.
Expected Time Complexity: O(X^{2} * 2^{N}), where X is average of summation B/arr_{i }for every number in the array.
Expected Auxiliary Space: O(X * 2^{N})
Constraints:
1 <= N <= 30
1 <= A[i] <= 20
1 <= B <= 100

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The restaurant AtCoder serves the following five dishes:
 - ABC Don (rice bowl): takes A minutes to serve.
 - ARC Curry: takes B minutes to serve.
 - AGC Pasta: takes C minutes to serve.
 - APC Ramen: takes D minutes to serve.
 - ATC Hanbagu (hamburger patty): takes E minutes to serve.
Here, the time to serve a dish is the time between when an order is placed and when the dish is delivered.
This restaurant has the following rules on orders:
 - An order can only be placed at a time that is a multiple of 10 (time 0, 10, 20, ...).
 - Only one dish can be ordered at a time.
 - No new order can be placed when an order is already placed and the dish is still not delivered, but a new order can be placed at the exact time when the dish is delivered.
E869120 arrives at this restaurant at time 0. He will order all five dishes. Find the earliest possible time for the last dish to be delivered.

Here, he can order the dishes in any order he likes, and he can place an order already at time 0.

-----Constraints-----
 - A, B, C, D and E are integers between 1 and 123 (inclusive).

-----Input-----
Input is given from Standard Input in the following format:
A
B
C
D
E

-----Output-----
Print the earliest possible time for the last dish to be delivered, as an integer.

-----Sample Input-----
29
20
7
35
120

-----Sample Output-----
215

If we decide to order the dishes in the order ABC Don, ARC Curry, AGC Pasta, ATC Hanbagu, APC Ramen, the earliest possible time for each order is as follows:
 - Order ABC Don at time 0, which will be delivered at time 29.
 - Order ARC Curry at time 30, which will be delivered at time 50.
 - Order AGC Pasta at time 50, which will be delivered at time 57.
 - Order ATC Hanbagu at time 60, which will be delivered at time 180.
 - Order APC Ramen at time 180, which will be delivered at time 215.
There is no way to order the dishes in which the last dish will be delivered earlier than this.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given strings s and t. Find one longest string that is a subsequence of both s and t.

Constraints

* s and t are strings consisting of lowercase English letters.
* 1 \leq |s|, |t| \leq 3000

Input

Input is given from Standard Input in the following format:


s
t


Output

Print one longest string that is a subsequence of both s and t. If there are multiple such strings, any of them will be accepted.

Examples

Input

axyb
abyxb


Output

axb


Input

aa
xayaz


Output

aa


Input

a
z


Output




Input

abracadabra
avadakedavra


Output

aaadara

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a square grid of size n × n. Some cells are colored in black, all others are colored in white. In one operation you can select some rectangle and color all its cells in white. It costs min(h, w) to color a rectangle of size h × w. You are to make all cells white for minimum total cost.

The square is large, so we give it to you in a compressed way. The set of black cells is the union of m rectangles.

Input

The first line contains two integers n and m (1 ≤ n ≤ 10^{9}, 0 ≤ m ≤ 50) — the size of the square grid and the number of black rectangles.

Each of the next m lines contains 4 integers x_{i1} y_{i1} x_{i2} y_{i2} (1 ≤ x_{i1} ≤ x_{i2} ≤ n, 1 ≤ y_{i1} ≤ y_{i2} ≤ n) — the coordinates of the bottom-left and the top-right corner cells of the i-th black rectangle.

The rectangles may intersect.

Output

Print a single integer — the minimum total cost of painting the whole square in white.

Examples

Input


10 2
4 1 5 10
1 4 10 5


Output


4


Input


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


Output


3

Note

The examples and some of optimal solutions are shown on the pictures below.

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Demiurges Shambambukli and Mazukta love to watch the games of ordinary people. Today, they noticed two men who play the following game.

There is a rooted tree on n nodes, m of which are leaves (a leaf is a nodes that does not have any children), edges of the tree are directed from parent to children. In the leaves of the tree integers from 1 to m are placed in such a way that each number appears exactly in one leaf.

Initially, the root of the tree contains a piece. Two players move this piece in turns, during a move a player moves the piece from its current nodes to one of its children; if the player can not make a move, the game ends immediately. The result of the game is the number placed in the leaf where a piece has completed its movement. The player who makes the first move tries to maximize the result of the game and the second player, on the contrary, tries to minimize the result. We can assume that both players move optimally well.

Demiurges are omnipotent, so before the game they can arbitrarily rearrange the numbers placed in the leaves. Shambambukli wants to rearrange numbers so that the result of the game when both players play optimally well is as large as possible, and Mazukta wants the result to be as small as possible. What will be the outcome of the game, if the numbers are rearranged by Shambambukli, and what will it be if the numbers are rearranged by Mazukta? Of course, the Demiurges choose the best possible option of arranging numbers.


-----Input-----

The first line contains a single integer n — the number of nodes in the tree (1 ≤ n ≤ 2·10^5).

Each of the next n - 1 lines contains two integers u_{i} and v_{i} (1 ≤ u_{i}, v_{i} ≤ n) — the ends of the edge of the tree; the edge leads from node u_{i} to node v_{i}. It is guaranteed that the described graph is a rooted tree, and the root is the node 1.


-----Output-----

Print two space-separated integers — the maximum possible and the minimum possible result of the game.


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

Output
3 2

Input
6
1 2
1 3
3 4
1 5
5 6

Output
3 3



-----Note-----

Consider the first sample. The tree contains three leaves: 3, 4 and 5. If we put the maximum number 3 at node 3, then the first player moves there and the result will be 3. On the other hand, it is easy to see that for any rearrangement the first player can guarantee the result of at least 2.

In the second sample no matter what the arragment is the first player can go along the path that ends with a leaf with number 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You're given an array $a$ of length $n$. You can perform the following operation on it as many times as you want:  Pick two integers $i$ and $j$ $(1 \le i,j \le n)$ such that $a_i+a_j$ is odd, then swap $a_i$ and $a_j$. 

What is lexicographically the smallest array you can obtain?

An array $x$ is lexicographically smaller than an array $y$ if there exists an index $i$ such that $x_i<y_i$, and $x_j=y_j$ for all $1 \le j < i$. Less formally, at the first index $i$ in which they differ, $x_i<y_i$


-----Input-----

The first line contains an integer $n$ ($1 \le n \le 10^5$) — the number of elements in the array $a$.

The second line contains $n$ space-separated integers $a_1$, $a_2$, $\ldots$, $a_{n}$ ($1 \le a_i \le 10^9$) — the elements of the array $a$.


-----Output-----

The only line contains $n$ space-separated integers, the lexicographically smallest array you can obtain.


-----Examples-----
Input
3
4 1 7

Output
1 4 7 
Input
2
1 1

Output
1 1 


-----Note-----

In the first example, we can swap $1$ and $4$ since $1+4=5$, which is odd.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Today, hedgehog Filya went to school for the very first time! Teacher gave him a homework which Filya was unable to complete without your help.

Filya is given an array of non-negative integers *a*1,<=*a*2,<=...,<=*a**n*. First, he pick an integer *x* and then he adds *x* to some elements of the array (no more than once), subtract *x* from some other elements (also, no more than once) and do no change other elements. He wants all elements of the array to be equal.

Now he wonders if it's possible to pick such integer *x* and change some elements of the array using this *x* in order to make all elements equal.

Input Specification:
The first line of the input contains an integer *n* (1<=≤<=*n*<=≤<=100<=000) — the number of integers in the Filya's array. The second line contains *n* integers *a*1,<=*a*2,<=...,<=*a**n* (0<=≤<=*a**i*<=≤<=109) — elements of the array.

Output Specification:
If it's impossible to make all elements of the array equal using the process given in the problem statement, then print "NO" (without quotes) in the only line of the output. Otherwise print "YES" (without quotes).

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

Demo Output:
['YES\n', 'NO\n']

Note:
In the first sample Filya should select *x* = 1, then add it to the first and the last elements of the array and subtract from the second and the third elements.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Everyone knows that 2010 FIFA World Cup is being held in South Africa now. By the decision of BFA (Berland's Football Association) next World Cup will be held in Berland. BFA took the decision to change some World Cup regulations:

  * the final tournament features n teams (n is always even) 
  * the first n / 2 teams (according to the standings) come through to the knockout stage 
  * the standings are made on the following principle: for a victory a team gets 3 points, for a draw — 1 point, for a defeat — 0 points. In the first place, teams are ordered in the standings in decreasing order of their points; in the second place — in decreasing order of the difference between scored and missed goals; in the third place — in the decreasing order of scored goals 
  * it's written in Berland's Constitution that the previous regulation helps to order the teams without ambiguity. 



You are asked to write a program that, by the given list of the competing teams and the results of all the matches, will find the list of teams that managed to get through to the knockout stage.

Input

The first input line contains the only integer n (1 ≤ n ≤ 50) — amount of the teams, taking part in the final tournament of World Cup. The following n lines contain the names of these teams, a name is a string of lower-case and upper-case Latin letters, its length doesn't exceed 30 characters. The following n·(n - 1) / 2 lines describe the held matches in the format name1-name2 num1:num2, where name1, name2 — names of the teams; num1, num2 (0 ≤ num1, num2 ≤ 100) — amount of the goals, scored by the corresponding teams. Accuracy of the descriptions is guaranteed: there are no two team names coinciding accurate to the letters' case; there is no match, where a team plays with itself; each match is met in the descriptions only once.

Output

Output n / 2 lines — names of the teams, which managed to get through to the knockout stage in lexicographical order. Output each name in a separate line. No odd characters (including spaces) are allowed. It's guaranteed that the described regulations help to order the teams without ambiguity.

Examples

Input

4
A
B
C
D
A-B 1:1
A-C 2:2
A-D 1:0
B-C 1:0
B-D 0:3
C-D 0:3


Output

A
D


Input

2
a
A
a-A 2:1


Output

a

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ashish has a tree consisting of $n$ nodes numbered $1$ to $n$ rooted at node $1$. The $i$-th node in the tree has a cost $a_i$, and binary digit $b_i$ is written in it. He wants to have binary digit $c_i$ written in the $i$-th node in the end.

To achieve this, he can perform the following operation any number of times:   Select any $k$ nodes from the subtree of any node $u$, and shuffle the digits in these nodes as he wishes, incurring a cost of $k \cdot a_u$. Here, he can choose $k$ ranging from $1$ to the size of the subtree of $u$. 

He wants to perform the operations in such a way that every node finally has the digit corresponding to its target.

Help him find the minimum total cost he needs to spend so that after all the operations, every node $u$ has digit $c_u$ written in it, or determine that it is impossible.


-----Input-----

First line contains a single integer $n$ $(1 \le n \le 2 \cdot 10^5)$ denoting the number of nodes in the tree.

$i$-th line of the next $n$ lines contains 3 space-separated integers $a_i$, $b_i$, $c_i$ $(1 \leq a_i \leq 10^9, 0 \leq b_i, c_i \leq 1)$  — the cost of the $i$-th node, its initial digit and its goal digit.

Each of the next $n - 1$ lines contain two integers $u$, $v$ $(1 \leq u, v \leq n, \text{ } u \ne v)$, meaning that there is an edge between nodes $u$ and $v$ in the tree.


-----Output-----

Print the minimum total cost to make every node reach its target digit, and $-1$ if it is impossible.


-----Examples-----
Input
5
1 0 1
20 1 0
300 0 1
4000 0 0
50000 1 0
1 2
2 3
2 4
1 5

Output
4
Input
5
10000 0 1
2000 1 0
300 0 1
40 0 0
1 1 0
1 2
2 3
2 4
1 5

Output
24000
Input
2
109 0 1
205 0 1
1 2

Output
-1


-----Note-----

The tree corresponding to samples $1$ and $2$ are: [Image]

In sample $1$, we can choose node $1$ and $k = 4$ for a cost of $4 \cdot 1$ = $4$ and select nodes ${1, 2, 3, 5}$, shuffle their digits and get the desired digits in every node.

In sample $2$, we can choose node $1$ and $k = 2$ for a cost of $10000 \cdot 2$, select nodes ${1, 5}$ and exchange their digits, and similarly, choose node $2$ and $k = 2$ for a cost of $2000 \cdot 2$, select nodes ${2, 3}$ and exchange their digits to get the desired digits in every node.

In sample $3$, it is impossible to get the desired digits, because there is no node with digit $1$ initially.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Theatre Square in the capital city of Berland has a rectangular shape with the size n × m meters. On the occasion of the city's anniversary, a decision was taken to pave the Square with square granite flagstones. Each flagstone is of the size a × a.
What is the least number of flagstones needed to pave the Square? It's allowed to cover the surface larger than the Theatre Square, but the Square has to be covered. It's not allowed to break the flagstones. The sides of flagstones should be parallel to the sides of the Square.
Input
The input contains three positive integer numbers in the first line: n,  m and a (1 ≤  n, m, a ≤ 10^9).
Output
Print the needed number of flagstones in new line.
Examples
input
6 6 4
output
4

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
A big company decided to launch a new series of rectangular displays, and decided that the display must have exactly *n* pixels. 

Your task is to determine the size of the rectangular display — the number of lines (rows) of pixels *a* and the number of columns of pixels *b*, so that:
 -  there are exactly *n* pixels on the display; -  the number of rows does not exceed the number of columns, it means *a*<=≤<=*b*; -  the difference *b*<=-<=*a* is as small as possible.

Input Specification:
The first line contains the positive integer *n* (1<=≤<=*n*<=≤<=106) — the number of pixels display should have.

Output Specification:
Print two integers — the number of rows and columns on the display.

Demo Input:
['8\n', '64\n', '5\n', '999999\n']

Demo Output:
['2 4\n', '8 8\n', '1 5\n', '999 1001\n']

Note:
In the first example the minimum possible difference equals 2, so on the display should be 2 rows of 4 pixels.

In the second example the minimum possible difference equals 0, so on the display should be 8 rows of 8 pixels.

In the third example the minimum possible difference equals 4, so on the display should be 1 row of 5 pixels.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
People are going to the movies in groups (or alone), but normally only care to socialize within that group. Being Scandinavian, each group of people would like to sit at least one space apart from any other group of people to ensure their privacy, unless of course they sit at the end of a row. The number of seats per row in the cinema starts at $X$ and decreases with one seat per row (down to a number of $1$ seat per row). The number of groups of varying sizes is given as a vector $(N_1, \ldots , N_ n)$, where $N_1$ is the number of people going alone, $N_2$ is the number of people going as a pair etc. Calculate the seat-width, $X$, of the widest row, which will create a solution that seats all (groups of) visitors using as few rows of seats as possible. The cinema also has a limited capacity, so the widest row may not exceed $12$ seats.

-----Input-----
The first line of input contains a single integer $n$ ($1 \leq n \leq 12$), giving the size of the largest group in the test case.

Then follows a line with $n$ non-negative integers, the $i$-th integer ($1$-indexed) denoting the number of groups of $i$ persons who need to be seated. Each such number is at most $30$, and not all of them are $0$.

-----Output-----
A single number; the size of the smallest widest row that will accommodate all the guests. If this number is greater than $12$, output impossible instead.

-----Examples-----
Sample Input:
3
0 1 1
Sample Output:
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Task
 In the Land Of Chess, bishops don't really like each other. In fact, when two bishops happen to stand on the same diagonal, they immediately rush towards the opposite ends of that same diagonal.

 Given the initial positions (in chess notation) of two bishops, `bishop1` and `bishop2`, calculate their future positions. Keep in mind that bishops won't move unless they see each other along the same diagonal.

# Example

 For `bishop1 = "d7" and bishop2 = "f5"`, the output should be `["c8", "h3"]`.

 ![](https://codefightsuserpics.s3.amazonaws.com/tasks/bishopDiagonal/img/ex_1.jpg?_tm=1473766087137)

 For `bishop1 = "d8" and bishop2 = "b5"`, the output should be `["b5", "d8"]`.

 The bishops don't belong to the same diagonal, so they don't move.

 ![](https://codefightsuserpics.s3.amazonaws.com/tasks/bishopDiagonal/img/ex_2.jpg?_tm=1473766087425)

# Input/Output


 - `[input]` string `bishop1`

    Coordinates of the first bishop in chess notation.


 - `[input]` string `bishop2`

    Coordinates of the second bishop in the same notation.


 - `[output]` a string array

    Coordinates of the bishops in lexicographical order after they check the diagonals they stand on.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a grid with $R$ rows (numbered $1$ through $R$) and $C$ columns (numbered $1$ through $C$). Initially, each cell of this grid is either empty, contains an ant or an anteater. Each ant is moving in a fixed direction: up, down, left or right. The anteaters do not move.
The movement of ants happens in discrete steps. For example, when an ant is in the cell in the $i$-th row and $j$-th column at some point in time (in some step) and it is moving down, then in the next step, it enters the cell in the $(i+1)$-th row and $j$-th column. Two ants meet each other when they enter the same cell at the same point in time (in the same step). When ants meet, they do not interact in any way and keep moving in their fixed directions.
If an ant reaches an anteater, that anteater eats the ant, so the ant completely disappears. If an ant attempts to leave the grid, it also disappears. When two ants enter a cell containing an anteater at the same time, they are eaten before they could meet.
Calculate the total number of pairs of ants that meet each other.

-----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 $R$ and $C$.
- Each of the following $R$ lines contains a single string with length $C$. For each valid $i, j$, the $j$-th character in the $i$-th string is:
- '#' if the cell in the $i$-th row and $j$-th column of the grid contains an anteater
- 'U', 'D', 'L' or 'R' if this cell contains an ant moving up, down, left or right respectively
- '-' if this cell is empty

-----Output-----
For each test case, print a single line containing one integer — the number of pairs of ants that meet.

-----Constraints-----
- $1 \le T \le 10$
- $1 \le R, C \le 50$
- each string contains only characters 'U', 'D', 'L', 'R', '#' and '-'

-----Example Input-----
10
3 3
R--
---
--U
1 4
R--R
2 2
--
--
1 4
R--L
1 4
-R-L
1 4
-R#L
3 3
R-D
-#-
R-U
3 3
R-D
---
R#U
3 3
-D-
R-L
-U-
1 7
RLLLLLL

-----Example Output-----
1
0
0
0
1
0
3
2
6
3

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