vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
On a two-dimensional plane, there are N red points and N blue points.
The coordinates of the i-th red point are (a_i, b_i), and the coordinates of the i-th blue point are (c_i, d_i).
A red point and a blue point can form a friendly pair when, the x-coordinate of the red point is smaller than that of the blue point, and the y-coordinate of the red point is also smaller than that of the blue point.
At most how many friendly pairs can you form? Note that a point cannot belong to multiple pairs.

-----Constraints-----
 - All input values are integers.
 - 1 \leq N \leq 100
 - 0 \leq a_i, b_i, c_i, d_i < 2N
 - a_1, a_2, ..., a_N, c_1, c_2, ..., c_N are all different.
 - b_1, b_2, ..., b_N, d_1, d_2, ..., d_N are all different.

-----Input-----
Input is given from Standard Input in the following format:
N
a_1 b_1
a_2 b_2
:
a_N b_N
c_1 d_1
c_2 d_2
:
c_N d_N

-----Output-----
Print the maximum number of friendly pairs.

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

-----Sample Output-----
2

For example, you can pair (2, 0) and (4, 2), then (3, 1) and (5, 5).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sumit and Dhiraj are roommates in a hostel of NIT Jamshedpur,One day after completing there boring assignments of Artificial Intelligence, they decided to play a game as it was dhiraj,s idea to play a game so he started explaining the rules of the game to sumit.
So the game was as follows-They randomly took a number N after that they find all its divisors.Suppose first sumit took a divisor then dhiraj and so on.The player who will be having the last divisor with him will win the game.Rohit their mutual friend,was observing them play. Can you help Rohit predict the outcome of game? If Sumit wins print "YES" without quotes and "NO" without quotes, if Dhiraj wins
the game.

-----Input-----
Input starts with an integer T denoting the number of test cases Each test case starts with a line containing an integer N the number.

-----Output-----
Outcome of each game in a separate line

-----Constraints-----
- 1 ≤ T ≤ 10^3
- 1 ≤ N ≤ 10^18

-----Sub tasks-----
- Subtask #1:(10 points)

- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 103
- Subtask #2:(25 points)

- 1 ≤ T ≤ 50
- 1 ≤ N ≤ 1016
- Subtask #3:(65 points)

- 1 ≤ T ≤ 103
- 1 ≤ N ≤ 1018

-----Example-----
Input:
2
4
5

Output:
YES
NO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this kata the function returns an array/list of numbers without its last element. The function is already written for you and the basic tests pass, but random tests fail. Your task is to figure out why and fix it.

Good luck!

Hint: watch out for side effects.

~~~if:javascript
Some good reading: [MDN Docs about arrays](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array)
~~~
~~~if:python
Some good reading: [Python Lists](http://www.compciv.org/guides/python/fundamentals/lists-mutability/)
~~~

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Local authorities have heard a lot about combinatorial abilities of Ostap Bender so they decided to ask his help in the question of urbanization. There are n people who plan to move to the cities. The wealth of the i of them is equal to a_{i}. Authorities plan to build two cities, first for n_1 people and second for n_2 people. Of course, each of n candidates can settle in only one of the cities. Thus, first some subset of candidates of size n_1 settle in the first city and then some subset of size n_2 is chosen among the remaining candidates and the move to the second city. All other candidates receive an official refuse and go back home.

To make the statistic of local region look better in the eyes of their bosses, local authorities decided to pick subsets of candidates in such a way that the sum of arithmetic mean of wealth of people in each of the cities is as large as possible. Arithmetic mean of wealth in one city is the sum of wealth a_{i} among all its residents divided by the number of them (n_1 or n_2 depending on the city). The division should be done in real numbers without any rounding.

Please, help authorities find the optimal way to pick residents for two cities.


-----Input-----

The first line of the input contains three integers n, n_1 and n_2 (1 ≤ n, n_1, n_2 ≤ 100 000, n_1 + n_2 ≤ n) — the number of candidates who want to move to the cities, the planned number of residents of the first city and the planned number of residents of the second city.

The second line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 100 000), the i-th of them is equal to the wealth of the i-th candidate.


-----Output-----

Print one real value — the maximum possible sum of arithmetic means of wealth of cities' residents. You answer will be considered correct if its absolute or relative error does not exceed 10^{ - 6}. 

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if $\frac{|a - b|}{\operatorname{max}(1, b)} \leq 10^{-6}$.


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

Output
6.00000000

Input
4 2 1
1 4 2 3

Output
6.50000000



-----Note-----

In the first sample, one of the optimal solutions is to move candidate 1 to the first city and candidate 2 to the second.

In the second sample, the optimal solution is to pick candidates 3 and 4 for the first city, and candidate 2 for the second one. Thus we obtain (a_3 + a_4) / 2 + a_2 = (3 + 2) / 2 + 4 = 6.5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
After you had helped George and Alex to move in the dorm, they went to help their friend Fedor play a new computer game «Call of Soldiers 3».

The game has (m + 1) players and n types of soldiers in total. Players «Call of Soldiers 3» are numbered form 1 to (m + 1). Types of soldiers are numbered from 0 to n - 1. Each player has an army. Army of the i-th player can be described by non-negative integer xi. Consider binary representation of xi: if the j-th bit of number xi equal to one, then the army of the i-th player has soldiers of the j-th type. 

Fedor is the (m + 1)-th player of the game. He assume that two players can become friends if their armies differ in at most k types of soldiers (in other words, binary representations of the corresponding numbers differ in at most k bits). Help Fedor and count how many players can become his friends.

Input

The first line contains three integers n, m, k (1 ≤ k ≤ n ≤ 20; 1 ≤ m ≤ 1000).

The i-th of the next (m + 1) lines contains a single integer xi (1 ≤ xi ≤ 2n - 1), that describes the i-th player's army. We remind you that Fedor is the (m + 1)-th player.

Output

Print a single integer — the number of Fedor's potential friends.

Examples

Input

7 3 1
8
5
111
17


Output

0


Input

3 3 3
1
2
3
4


Output

3

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
One day, after a difficult lecture a diligent student Sasha saw a graffitied desk in the classroom. She came closer and read: "Find such positive integer *n*, that among numbers *n*<=+<=1, *n*<=+<=2, ..., 2·*n* there are exactly *m* numbers which binary representation contains exactly *k* digits one".

The girl got interested in the task and she asked you to help her solve it. Sasha knows that you are afraid of large numbers, so she guaranteed that there is an answer that doesn't exceed 1018.

Input Specification:
The first line contains two space-separated integers, *m* and *k* (0<=≤<=*m*<=≤<=1018; 1<=≤<=*k*<=≤<=64).

Output Specification:
Print the required number *n* (1<=≤<=*n*<=≤<=1018). If there are multiple answers, print any of them.

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

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Shrimpy Duc is a fat and greedy boy who is always hungry. After a while of searching for food to satisfy his never-ending hunger, Shrimpy Duc finds M&M candies lying unguarded on a L × L grid. There are n M&M candies on the grid, the i-th M&M is currently located at (x_i + 0.5, y_i + 0.5), and has color c_i out of a total of k colors (the size of M&Ms are insignificant).

Shrimpy Duc wants to steal a rectangle of M&Ms, specifically, he wants to select a rectangle with integer coordinates within the grid and steal all candies within the rectangle. Shrimpy Duc doesn't need to steal every single candy, however, he would like to steal at least one candy for each color.

In other words, he wants to select a rectangle whose sides are parallel to the coordinate axes and whose left-bottom vertex (X_1, Y_1) and right-top vertex (X_2, Y_2) are points with integer coordinates satisfying 0 ≤ X_1 < X_2 ≤ L and 0 ≤ Y_1 < Y_2 ≤ L, so that for every color 1 ≤ c ≤ k there is at least one M&M with color c that lies within that rectangle.

How many such rectangles are there? This number may be large, so you only need to find it modulo 10^9 + 7.

Input

The first line contains three positive integers n, k, L (1 ≤ k ≤ n ≤ 2 ⋅ 10^3, 1 ≤ L ≤ 10^9 ) — the number of M&Ms, the number of colors and the length of the grid respectively.

The following n points describe the M&Ms. Each line contains three integers x_i, y_i, c_i (0 ≤ x_i, y_i < L, 1 ≤ c_i ≤ k) — the coordinates and color of the i-th M&M respectively. 

Different M&Ms have different coordinates (x_i ≠ x_j or y_i ≠ y_j for every i ≠ j), and for every 1 ≤ c ≤ k there is at least one M&M with color c.

Output

Output a single integer — the number of rectangles satisfying Shrimpy Duc's conditions, modulo 10^9 + 7.

Examples

Input


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


Output


20


Input


5 3 10
6 5 3
5 3 1
7 9 1
2 3 2
5 0 2


Output


300


Input


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


Output


226

Note

Grid for the first sample:

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A student's life is fraught with complications. Some Berland University students know this only too well. Having studied for two years, they contracted strong antipathy towards the chairperson of some department. Indeed, the person in question wasn't the kindest of ladies to begin with: prone to reforming groups, banning automatic passes and other mean deeds. At last the students decided that she just can't get away with all this anymore...

The students pulled some strings on the higher levels and learned that the next University directors' meeting is going to discuss n orders about the chairperson and accept exactly p of them. There are two values assigned to each order: ai is the number of the chairperson's hairs that turn grey if she obeys the order and bi — the displeasement of the directors if the order isn't obeyed. The students may make the directors pass any p orders chosen by them. The students know that the chairperson will obey exactly k out of these p orders. She will pick the orders to obey in the way that minimizes first, the directors' displeasement and second, the number of hairs on her head that turn grey.

The students want to choose p orders in the way that maximizes the number of hairs on the chairperson's head that turn grey. If there are multiple ways to accept the orders, then the students are keen on maximizing the directors' displeasement with the chairperson's actions. Help them.

Input

The first line contains three integers n (1 ≤ n ≤ 105), p (1 ≤ p ≤ n), k (1 ≤ k ≤ p) — the number of orders the directors are going to discuss, the number of orders to pass and the number of orders to be obeyed by the chairperson, correspondingly. Each of the following n lines contains two integers ai and bi (1 ≤ ai, bi ≤ 109), describing the corresponding order.

Output

Print in an arbitrary order p distinct integers — the numbers of the orders to accept so that the students could carry out the revenge. The orders are indexed from 1 to n in the order they occur in the input. If there are multiple solutions, you can print any of them.

Examples

Input

5 3 2
5 6
5 8
1 3
4 3
4 11


Output

3 1 2 

Input

5 3 3
10 18
18 17
10 20
20 18
20 18


Output

2 4 5 

Note

In the first sample one of optimal solutions is to pass orders 1, 2, 3. In this case the chairperson obeys orders number 1 and 2. She gets 10 new grey hairs in the head and the directors' displeasement will equal 3. Note that the same result can be achieved with order 4 instead of order 3.

In the second sample, the chairperson can obey all the orders, so the best strategy for the students is to pick the orders with the maximum sum of ai values. The chairperson gets 58 new gray hairs and the directors' displeasement will equal 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
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. [Image] There are $6$ connected components, $2$ of them are cycles: $[7, 10, 16]$ and $[5, 11, 9, 15]$. 


-----Input-----

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-----

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


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

Output
1

Input
17 15
1 8
1 12
5 11
11 9
9 15
15 5
4 13
3 13
4 3
10 16
7 10
16 7
14 3
14 4
17 6

Output
2



-----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.
Given a singly linked list, the task is to rearrange it in a way that all odd position nodes are together and all even positions node are together.
Assume the first element to be at position 1 followed by second element at position 2 and so on.
Note: You should place all odd positioned nodes first and then the even positioned ones. (considering 1 based indexing). Also, the relative order of odd positioned nodes and even positioned nodes should be maintained.
Example 1:
Input:
LinkedList: 1->2->3->4
Output: 1 3 2 4 
Explanation: 
Odd elements are 1, 3 and even elements are 
2, 4. Hence, resultant linked list is 
1->3->2->4.
Example 2:
Input:
LinkedList: 1->2->3->4->5
Output: 1 3 5 2 4 
Explanation: 
Odd elements are 1, 3, 5 and even elements are
2, 4. Hence, resultant linked list is
1->3->5->2->4.
Your Task:
The task is to complete the function rearrangeEvenOdd() which rearranges the nodes in the linked list as required and doesn't return anything.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1 ≤ Size of the linked list ≤ 10^{4}
0 ≤ value of linked list ≤ 10^{3}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Archith loves to play with number series. Archith asked his girlfriend to a date. But she was busy in solving the homework on triangular series which stated that find the least number which has higher divisors than n in a triangular series. His girlfriend made a condition that if he solves this assignment for her she will come for date. Archith dont want to waste time he is developing a code. Put yourself in the position of archith and solve this problem.(#projecteuler 13)

INPUT:
T test cases
every t lines consists of a number n which specifies the no of divisors.
OUTPUT:
output the least triangular number which has higher no of divisors than n.

1<T<11
1<n<10^2

example:

triangular series will be as follows 1,3,6,10........
if n =2
6 has 4 divisors.So 6 will be the least number to have more than n divisors.

SAMPLE INPUT
4
1
2
3
4

SAMPLE OUTPUT
3
6
6
28

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Create a function `close_compare` that accepts 3 parameters: `a`, `b`, and an optional `margin`. The function should return whether `a` is lower than, close to, or higher than `b`. `a` is "close to" `b` if `margin` is higher than or equal to the difference between `a` and `b`.

When `a` is lower than `b`, return `-1`.

When `a` is higher than `b`, return `1`.

When `a` is close to `b`, return `0`.

If `margin` is not given, treat it as zero.

Example: if `a = 3`, `b = 5` and the `margin = 3`, since `a` and `b` are no more than 3 apart, `close_compare` should return `0`. Otherwise, if instead `margin = 0`, `a` is lower than `b` and `close_compare` should return `-1`.

Assume: `margin >= 0`

Tip: Some languages have a way to make arguments optional.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are a treasure hunter searching for gold in the wild. Luckily you got a map of the area from a black marketeer. The map clearly shows where a box of gold is along with the surrounding terrain. Of course, you want to head to the treasure as fast as possible. However, the trip might not be easy.

The area is described by a grid of $N$ rows and $M$ columns. You are currently located at the cell labeled ‘S’. The treasure is located at the cell labeled ‘G’. Despite your eagerness for the treasure, you cannot keep moving tirelessly. The surrounding area has different landforms: plain (‘.’), forest (‘F’), mountain (‘M’) or river (‘#’). Rivers are impassable since no boats are currently available. You can navigate in four directions (up, down, left, right) between neighboring cells.

At the beginning of your trip you have $K$ stamina points. Moving onto a plain, forest, and mountain costs you $1$, $2$, and $3$ points of stamina respectively. Once you run out of stamina and can no longer move to nearby cells, you must camp and rest. Your stamina is replenished to the full $K$ points on the second day so that you can start moving again.

Plan wisely with the map and determine the minimum number of days you need to reach the treasure.

-----Input-----
The first line has three integers $N$, $M$ ($1\leq N, M \leq 50$), and $K$ ($1 \leq K \leq 100$). Each of the next $N$ lines has $M$ characters describing the grid shown by the treasure map. The grid contains only characters ‘.’, ‘F’, ‘M’, ‘#’, ‘S’, and ‘G’. It is guaranteed that ‘S’ and ‘G’ appear exactly once in the grid. You may assume your starting point (‘S’) and the treasure (‘G’) are both on a plain.

-----Output-----
Output the minimum number of days you need to reach the treasure. If it is impossible to get to the treasure, output “-1”.

-----Examples-----
Sample Input 1:
2 5 4
S#.F.
.MFMG
Sample Output 1:
3

Sample Input 2:
1 2 1
GS
Sample Output 2:
1

Sample Input 3:
2 2 10
S#
#G
Sample Output 3:
-1

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Tyndex is again well ahead of the rivals! The reaction to the release of Zoozle Chrome browser was the release of a new browser Tyndex.Brome!

The popularity of the new browser is growing daily. And the secret is not even the Tyndex.Bar installed (the Tyndex.Bar automatically fills the glass with the finest 1664 cognac after you buy Tyndex.Bottles and insert in into a USB port). It is highly popular due to the well-thought interaction with the user.

Let us take, for example, the system of automatic address correction. Have you entered codehorses instead of codeforces? The gloomy Zoozle Chrome will sadly say that the address does not exist. Tyndex.Brome at the same time will automatically find the closest address and sent you there. That's brilliant!

How does this splendid function work? That's simple! For each potential address a function of the *F* error is calculated by the following rules:
 -  for every letter *c**i* from the potential address *c* the closest position *j* of the letter *c**i* in the address (*s*) entered by the user is found. The absolute difference |*i*<=-<=*j*| of these positions is added to *F*. So for every *i* (1<=≤<=*i*<=≤<=|*c*|) the position *j* is chosen such, that *c**i*<==<=*s**j*, and |*i*<=-<=*j*| is minimal possible. -  if no such letter *c**i* exists in the address entered by the user, then the length of the potential address |*c*| is added to *F*. 
After the values of the error function have been calculated for all the potential addresses the most suitable one is found. 

To understand the special features of the above described method better, it is recommended to realize the algorithm of calculating the *F* function for an address given by the user and some set of potential addresses. Good luck!

Input Specification:
The first line contains two integers *n* and *k* (1<=≤<=*n*<=≤<=105,<=1<=≤<=*k*<=≤<=105). They are the number of potential addresses and the length of the address entered by the user. The next line contains *k* lowercase Latin letters. They are the address entered by the user (*s*). Each next *i*-th (1<=≤<=*i*<=≤<=*n*) line contains a non-empty sequence of lowercase Latin letters. They are the potential address. It is guaranteed that the total length of all the lines does not exceed 2·105.

Output Specification:
On each *n* line of the output file print a single number: the value of the error function when the current potential address is chosen.

Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cout (also you may use %I64d).

Demo Input:
['2 10\ncodeforces\ncodeforces\ncodehorses\n', '9 9\nvkontakte\nvcontacte\nvkontrakte\nvkollapse\nvkrokodile\nvtopke\nvkapuste\nvpechke\nvk\nvcodeforcese\n']

Demo Output:
['0\n12\n', '18\n14\n36\n47\n14\n29\n30\n0\n84\n']

Note:
none

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