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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
For a connected undirected weighted graph *G*, MST (minimum spanning tree) is a subgraph of *G* that contains all of *G*'s vertices, is a tree, and sum of its edges is minimum possible.

You are given a graph *G*. If you run a MST algorithm on graph it would give you only one MST and it causes other edges to become jealous. You are given some queries, each query contains a set of edges of graph *G*, and you should determine whether there is a MST containing all these edges or not.

Input Specification:
The first line contains two integers *n*, *m* (2<=<=≤<=*n*,<=*m*<=<=≤<=5·105, *n*<=-<=1<=≤<=*m*) — the number of vertices and edges in the graph and the number of queries.

The *i*-th of the next *m* lines contains three integers *u**i*, *v**i*, *w**i* (*u**i*<=≠<=*v**i*, 1<=≤<=*w**i*<=≤<=5·105) — the endpoints and weight of the *i*-th edge. There can be more than one edges between two vertices. It's guaranteed that the given graph is connected.

The next line contains a single integer *q* (1<=≤<=*q*<=≤<=5·105) — the number of queries.

*q* lines follow, the *i*-th of them contains the *i*-th query. It starts with an integer *k**i* (1<=≤<=*k**i*<=≤<=*n*<=-<=1) — the size of edges subset and continues with *k**i* distinct space-separated integers from 1 to *m* — the indices of the edges. It is guaranteed that the sum of *k**i* for 1<=≤<=*i*<=≤<=*q* does not exceed 5·105.

Output Specification:
For each query you should print "YES" (without quotes) if there's a MST containing these edges and "NO" (of course without quotes again) otherwise.

Demo Input:
['5 7\n1 2 2\n1 3 2\n2 3 1\n2 4 1\n3 4 1\n3 5 2\n4 5 2\n4\n2 3 4\n3 3 4 5\n2 1 7\n2 1 2\n']

Demo Output:
['YES\nNO\nYES\nNO\n']

Note:
This is the graph of sample:

Weight of minimum spanning tree on this graph is 6.

MST with edges (1, 3, 4, 6), contains all of edges from the first query, so answer on the first query is "YES".

Edges from the second query form a cycle of length 3, so there is no spanning tree including these three edges. Thus, answer is "NO".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a binary tree. Your task is pretty straightforward. You have to find the sum of the product of each node and its mirror image (The mirror of a node is a node which exists at the mirror position of the node in opposite subtree at the root.). Don’t take into account a pair more than once. The root node is the mirror image of itself.
 
Example 1:
Input:
      4         
    /    \
   5      6
Output:
46
Explanation:
Sum = (4*4) + (5*6) = 46
Example 2:
Input:
                       1                 
                   /        \
                 3            2
                  /  \         /  \
              7     6       5    4
            /   \    \     /  \    \
          11    10    15  9    8    12
Output:
332
Explanation:
Sum = (1*1) + (3*2) + (7*4) + (6*5) + (11*12) + (15*9) = 332
 
Your Task:
You need to complete the function imgMultiply() that takes root as parameter and returns the required sum.The answer may be very large, compute the answer modulo 10^{9} + 7.
Expected Time Complexity: O(Number of nodes).
Expected Auxiliary Space: O(Height of the Tree).
Constraints:            
1 <= Number of nodes <= 10^{5}
1 <= Data of a node <= 10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are provided with an input containing a number. Implement a solution to find the largest sum of consecutive increasing digits , and present the output with the largest sum and the positon of start and end of the consecutive digits.
Example :
Input :> 8789651
Output :> 24:2-4
where 24 is the largest sum and 2-4 is start and end of the consecutive increasing digits.

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

It's your first day in the robot factory and your supervisor thinks that you should start with an easy task. So you are responsible for purchasing raw materials needed to produce the robots.

A complete robot weights `50` kilogram. Iron is the only material needed to create a robot. All iron is inserted in the first machine; the output of this machine is the input for the next one, and so on. The whole process is sequential. Unfortunately not all machines are first class, so a given percentage of their inputs are destroyed during processing.

# Task

You need to figure out how many kilograms of iron you need to buy to build the requested number of robots.

# Example

Three machines are used to create a robot. Each of them produces `10%` scrap. Your target is to deliver `90` robots.  
The method will be called with the following parameters:

```
CalculateScrap(scrapOfTheUsedMachines, numberOfRobotsToProduce)
CalculateScrap(int[] { 10, 10, 10 }, 90)
```

# Assumptions

* The scrap is less than `100%`.
* The scrap is never negative.
* There is at least one machine in the manufacturing line.
* Except for scrap there is no material lost during manufacturing.
* The number of produced robots is always a positive number.
* You can only buy full kilograms of iron.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp likes squares and cubes of positive integers. Here is the beginning of the sequence of numbers he likes: $1$, $4$, $8$, $9$, ....

For a given number $n$, count the number of integers from $1$ to $n$ that Polycarp likes. In other words, find the number of such $x$ that $x$ is a square of a positive integer number or a cube of a positive integer number (or both a square and a cube simultaneously).


-----Input-----

The first line contains an integer $t$ ($1 \le t \le 20$) — the number of test cases.

Then $t$ lines contain the test cases, one per line. Each of the lines contains one integer $n$ ($1 \le n \le 10^9$).


-----Output-----

For each test case, print the answer you are looking for — the number of integers from $1$ to $n$ that Polycarp likes.


-----Examples-----

Input
6
10
1
25
1000000000
999999999
500000000
Output
4
1
6
32591
32590
23125


-----Note-----

None

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Spongebob is already tired trying to reason his weird actions and calculations, so he simply asked you to find all pairs of n and m, such that there are exactly x distinct squares in the table consisting of n rows and m columns. For example, in a 3 × 5 table there are 15 squares with side one, 8 squares with side two and 3 squares with side three. The total number of distinct squares in a 3 × 5 table is 15 + 8 + 3 = 26.

Input

The first line of the input contains a single integer x (1 ≤ x ≤ 1018) — the number of squares inside the tables Spongebob is interested in.

Output

First print a single integer k — the number of tables with exactly x distinct squares inside.

Then print k pairs of integers describing the tables. Print the pairs in the order of increasing n, and in case of equality — in the order of increasing m.

Examples

Input

26


Output

6
1 26
2 9
3 5
5 3
9 2
26 1


Input

2


Output

2
1 2
2 1


Input

8


Output

4
1 8
2 3
3 2
8 1

Note

In a 1 × 2 table there are 2 1 × 1 squares. So, 2 distinct squares in total.

<image>

In a 2 × 3 table there are 6 1 × 1 squares and 2 2 × 2 squares. That is equal to 8 squares in total.

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You might have heard about the friendly interactive shell - fish. It’s terminal based, but a bit friendlier to new users who can’t remember the commands they typed before. Fish can use your history of commands for command completion: pressing up (“^”) finds the last command you ran that shares the prefix you have already typed (a string is a prefix of itself).

If you press up again you go another step back in time, finding the second last command that shares the prefix of what you typed. If there are no more matching commands you stay at the oldest matching command.

When a series of consecutive up-presses is ended, either by typing some other character or by pressing enter to run the current command, the matching command from the history replaces everything that was typed in the current input.

When you press enter the current input is added to the command history. The command history does not contain up-characters (“^”) since command completion is always performed before the enter-key is processed.

The input to this problem contains the characters a user typed in a fish terminal, separated into lines. After each line, the user pressed enter. Your task is to output the resulting command history.

-----Input-----
The first line of the input contains a single number $n$, where $1 \leq n \leq 100000$.

Then follows $n$ lines with the user input. Each line consists of characters from the alphabet $\big [$a-zA-Z0-9.^-$\big ]$, i.e. English lower and upper case letters, digits, “-”, “ ”, “.” and the symbol “^” denoting the up key. No command begins or ends with a space.

The input is guaranteed to contain at most $10^6$ characters.

-----Output-----
For each command in the input output a line with the completed command (where all “^” are expanded). The total amount of output is guaranteed to be at most $10^6$ characters.

-----Sample Explanation-----
In Sample Input $1$ your first command is “python”. Your next command gets auto completed to “python”, and then you write “ main.py”, which is appended to your command making “python main.py”. The last command completes the first up press to “python main.py”, then “ -n 10” is typed which becomes “python main.py -n 10”.

In Sample Input $2$ your first two commands are “python” and “java”. The third command becomes auto completed to java, your previous command. The fourth command completes to “python” since it was your third last command. For your fifth command the third last command auto completed is now “java”.

In Sample Input $3$ no commands are in your history, so your up presses have no effect and only the non up presses count to your command making “python”.

-----Examples-----
Sample Input 1:
3
python
p^ main.py
^ -n 10
Sample Output 1:
python
python main.py
python main.py -n 10

Sample Input 2:
5
python
java
^
^^^
^^^
Sample Output 2:
python
java
java
python
java

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Now you can take online courses in the Berland State University! Polycarp needs to pass k main online courses of his specialty to get a diploma. In total n courses are availiable for the passage.

The situation is complicated by the dependence of online courses, for each course there is a list of those that must be passed before starting this online course (the list can be empty, it means that there is no limitation).

Help Polycarp to pass the least number of courses in total to get the specialty (it means to pass all main and necessary courses). Write a program which prints the order of courses. 

Polycarp passes courses consistently, he starts the next course when he finishes the previous one. Each course can't be passed more than once. 


-----Input-----

The first line contains n and k (1 ≤ k ≤ n ≤ 10^5) — the number of online-courses and the number of main courses of Polycarp's specialty. 

The second line contains k distinct integers from 1 to n — numbers of main online-courses of Polycarp's specialty. 

Then n lines follow, each of them describes the next course: the i-th of them corresponds to the course i. Each line starts from the integer t_{i} (0 ≤ t_{i} ≤ n - 1) — the number of courses on which the i-th depends. Then there follows the sequence of t_{i} distinct integers from 1 to n — numbers of courses in random order, on which the i-th depends. It is guaranteed that no course can depend on itself. 

It is guaranteed that the sum of all values t_{i} doesn't exceed 10^5. 


-----Output-----

Print -1, if there is no the way to get a specialty. 

Otherwise, in the first line print the integer m — the minimum number of online-courses which it is necessary to pass to get a specialty. In the second line print m distinct integers — numbers of courses which it is necessary to pass in the chronological order of their passage. If there are several answers it is allowed to print any of them.


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

Output
5
1 2 3 4 5 

Input
9 3
3 9 5
0
0
3 9 4 5
0
0
1 8
1 6
1 2
2 1 2

Output
6
1 2 9 4 5 3 

Input
3 3
1 2 3
1 2
1 3
1 1

Output
-1



-----Note-----

In the first test firstly you can take courses number 1 and 2, after that you can take the course number 4, then you can take the course number 5, which is the main. After that you have to take only the course number 3, which is the last not passed main course.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A company of $n$ friends wants to order exactly two pizzas. It is known that in total there are $9$ pizza ingredients in nature, which are denoted by integers from $1$ to $9$.

Each of the $n$ friends has one or more favorite ingredients: the $i$-th of friends has the number of favorite ingredients equal to $f_i$ ($1 \le f_i \le 9$) and your favorite ingredients form the sequence $b_{i1}, b_{i2}, \dots, b_{if_i}$ ($1 \le b_{it} \le 9$).

The website of CodePizza restaurant has exactly $m$ ($m \ge 2$) pizzas. Each pizza is characterized by a set of $r_j$ ingredients $a_{j1}, a_{j2}, \dots, a_{jr_j}$ ($1 \le r_j \le 9$, $1 \le a_{jt} \le 9$) , which are included in it, and its price is $c_j$.

Help your friends choose exactly two pizzas in such a way as to please the maximum number of people in the company. It is known that a person is pleased with the choice if each of his/her favorite ingredients is in at least one ordered pizza. If there are several ways to choose two pizzas so as to please the maximum number of friends, then choose the one that minimizes the total price of two pizzas.


-----Input-----

The first line of the input contains two integers $n$ and $m$ ($1 \le n \le 10^5, 2 \le m \le 10^5$) — the number of friends in the company and the number of pizzas, respectively.

Next, the $n$ lines contain descriptions of favorite ingredients of the friends: the $i$-th of them contains the number of favorite ingredients $f_i$ ($1 \le f_i \le 9$) and a sequence of distinct integers $b_{i1}, b_{i2}, \dots, b_{if_i}$ ($1 \le b_{it} \le 9$).

Next, the $m$ lines contain pizza descriptions: the $j$-th of them contains the integer price of the pizza $c_j$ ($1 \le c_j \le 10^9$), the number of ingredients $r_j$ ($1 \le r_j \le 9$) and the ingredients themselves as a sequence of distinct integers $a_{j1}, a_{j2}, \dots, a_{jr_j}$ ($1 \le a_{jt} \le 9$).


-----Output-----

Output two integers $j_1$ and $j_2$ ($1 \le j_1,j_2 \le m$, $j_1 \ne j_2$) denoting the indices of two pizzas in the required set. If there are several solutions, output any of them. Pizza indices can be printed in any order.


-----Examples-----
Input
3 4
2 6 7
4 2 3 9 5
3 2 3 9
100 1 7
400 3 3 2 5
100 2 9 2
500 3 2 9 5

Output
2 3

Input
4 3
1 1
1 2
1 3
1 4
10 4 1 2 3 4
20 4 1 2 3 4
30 4 1 2 3 4

Output
1 2

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

Output
2 4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We need you to implement a method of receiving commands over a network, processing the information and responding.

Our device will send a single packet to you containing data and an instruction which you must perform before returning your reply.

To keep things simple, we will be passing a single "packet" as a string. 
Each "byte" contained in the packet is represented by 4 chars.



One packet is structured as below:
```
Header  Instruction   Data1    Data2   Footer
------   ------       ------   ------  ------
 H1H1     0F12         0012     0008    F4F4
------   ------       ------   ------  ------

The string received in this case would be - "H1H10F1200120008F4F4"

Instruction: The calculation you should perform, always one of the below.
            0F12 = Addition
            B7A2 = Subtraction
            C3D9 = Multiplication
            FFFF = This instruction code should be used to identify your return value.
``` 
- The Header and Footer are unique identifiers which you must use to form your reply.

- Data1 and Data2 are the decimal representation of the data you should apply your instruction to. _i.e 0109 = 109._

- Your response must include the received header/footer, a "FFFF" instruction code, and the result of your calculation stored in Data1.

- Data2 should be zero'd out to "0000".


```
To give a complete example:

If you receive message "H1H10F1200120008F4F4".
The correct response would be "H1H1FFFF00200000F4F4"

```
In the event that your calculation produces a negative result, the value returned should be "0000", similarily if the value is above 9999 you should return "9999".


Goodluck, I look forward to reading your creative solutions!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string S of opening and closing brackets '(' and ')' only. The task is to find an equal point. An equal point is an index such that the number of closing brackets on right from that point must be equal to number of opening brackets before that point.
Example 1:
Input: str = "(())))("
Output: 4
Explanation:
After index 4, string splits into (())
and ))(. Number of opening brackets in the
first part is equal to number of closing
brackets in the second part.
Example 2:
Input : str = "))"
Output: 2
Explanation:
As after 2nd position i.e. )) and "empty"
string will be split into these two parts:
So, in this number of opening brackets i.e.
0 in the first part is equal to number of
closing brackets in the second part i.e.
also 0.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function findIndex() which takes the string S as inputs and returns the occurrence of the equal point in the string.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ S ≤ 10^{6}
String can be unbalanced

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Eugeny has n cards, each of them has exactly one integer written on it. Eugeny wants to exchange some cards with Nikolay so that the number of even integers on his cards would equal the number of odd integers, and that all these numbers would be distinct. 

Nikolay has m cards, distinct numbers from 1 to m are written on them, one per card. It means that Nikolay has exactly one card with number 1, exactly one card with number 2 and so on. 

A single exchange is a process in which Eugeny gives one card to Nikolay and takes another one from those Nikolay has. Your task is to find the minimum number of card exchanges and determine which cards Eugeny should exchange.

Input

The first line contains two integers n and m (2 ≤ n ≤ 2·105, 1 ≤ m ≤ 109) — the number of cards Eugeny has and the number of cards Nikolay has. It is guaranteed that n is even.

The second line contains a sequence of n positive integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the numbers on Eugeny's cards.

Output

If there is no answer, print -1.

Otherwise, in the first line print the minimum number of exchanges. In the second line print n integers — Eugeny's cards after all the exchanges with Nikolay. The order of cards should coincide with the card's order in the input data. If the i-th card wasn't exchanged then the i-th number should coincide with the number from the input data. Otherwise, it is considered that this card was exchanged, and the i-th number should be equal to the number on the card it was exchanged to.

If there are multiple answers, it is allowed to print any of them.

Examples

Input

6 2
5 6 7 9 4 5


Output

1
5 6 7 9 4 2 


Input

8 6
7 7 7 7 8 8 8 8


Output

6
7 2 4 6 8 1 3 5 


Input

4 1
4 2 1 10


Output

-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have a canvas divided into a grid with H rows and W columns. The square at the i-th row from the top and the j-th column from the left is represented as (i, j).

Initially, all the squares are white. square1001 wants to draw a picture with black paint. His specific objective is to make Square (i, j) black when s_{i, j}= #, and to make Square (i, j) white when s_{i, j}= ..

However, since he is not a good painter, he can only choose two squares that are horizontally or vertically adjacent and paint those squares black, for some number of times (possibly zero). He may choose squares that are already painted black, in which case the color of those squares remain black.

Determine if square1001 can achieve his objective.  

-----Constraints-----
 - H is an integer between 1 and 50 (inclusive).
 - W is an integer between 1 and 50 (inclusive).
 - For every (i, j) (1 \leq i \leq H, 1 \leq j \leq W), s_{i, j} is # or ..

-----Input-----
Input is given from Standard Input in the following format:
H W
s_{1, 1} s_{1, 2} s_{1, 3} ... s_{1, W}
s_{2, 1} s_{2, 2} s_{2, 3} ... s_{2, W}
  :   :
s_{H, 1} s_{H, 2} s_{H, 3} ... s_{H, W}

-----Output-----
If square1001 can achieve his objective, print Yes; if he cannot, print No.

-----Sample Input-----
3 3
.#.
###
.#.

-----Sample Output-----
Yes

One possible way to achieve the objective is shown in the figure below. Here, the squares being painted are marked by stars.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Two boys decided to compete in text typing on the site "Key races". During the competition, they have to type a text consisting of *s* characters. The first participant types one character in *v*1 milliseconds and has ping *t*1 milliseconds. The second participant types one character in *v*2 milliseconds and has ping *t*2 milliseconds.

If connection ping (delay) is *t* milliseconds, the competition passes for a participant as follows: 
 1.  Exactly after *t* milliseconds after the start of the competition the participant receives the text to be entered. 1.  Right after that he starts to type it. 1.  Exactly *t* milliseconds after he ends typing all the text, the site receives information about it. 
The winner is the participant whose information on the success comes earlier. If the information comes from both participants at the same time, it is considered that there is a draw.

Given the length of the text and the information about participants, determine the result of the game.

Input Specification:
The first line contains five integers *s*, *v*1, *v*2, *t*1, *t*2 (1<=≤<=*s*,<=*v*1,<=*v*2,<=*t*1,<=*t*2<=≤<=1000) — the number of characters in the text, the time of typing one character for the first participant, the time of typing one character for the the second participant, the ping of the first participant and the ping of the second participant.

Output Specification:
If the first participant wins, print "First". If the second participant wins, print "Second". In case of a draw print "Friendship".

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

Demo Output:
['First\n', 'Second\n', 'Friendship\n']

Note:
In the first example, information on the success of the first participant comes in 7 milliseconds, of the second participant — in 14 milliseconds. So, the first wins.

In the second example, information on the success of the first participant comes in 11 milliseconds, of the second participant — in 5 milliseconds. So, the second wins.

In the third example, information on the success of the first participant comes in 22 milliseconds, of the second participant — in 22 milliseconds. So, it is be a draw.

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