vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You are given a directed graph consisting of $n$ vertices. Each directed edge (or arc) labeled with a single character. Initially, the graph is empty.

You should process $m$ queries with it. Each query is one of three types:

"$+$ $u$ $v$ $c$" — add arc from $u$ to $v$ with label $c$. It's guaranteed that there is no arc $(u, v)$ in the graph at this moment;

"$-$ $u$ $v$" — erase arc from $u$ to $v$. It's guaranteed that the graph contains arc $(u, v)$ at this moment;

"$?$ $k$" — find the sequence of $k$ vertices $v_1, v_2, \dots, v_k$ such that there exist both routes $v_1 \to v_2 \to \dots \to v_k$ and $v_k \to v_{k - 1} \to \dots \to v_1$ and if you write down characters along both routes you'll get the same string. You can visit the same vertices any number of times.


-----Input-----

The first line contains two integers $n$ and $m$ ($2 \le n \le 2 \cdot 10^5$; $1 \le m \le 2 \cdot 10^5$) — the number of vertices in the graph and the number of queries.

The next $m$ lines contain queries — one per line. Each query is one of three types:

"$+$ $u$ $v$ $c$" ($1 \le u, v \le n$; $u \neq v$; $c$ is a lowercase Latin letter);

"$-$ $u$ $v$" ($1 \le u, v \le n$; $u \neq v$);

"$?$ $k$" ($2 \le k \le 10^5$).

It's guaranteed that you don't add multiple edges and erase only existing edges. Also, there is at least one query of the third type.


-----Output-----

For each query of the third type, print YES if there exist the sequence $v_1, v_2, \dots, v_k$ described above, or NO otherwise.


-----Examples-----

Input
3 11
+ 1 2 a
+ 2 3 b
+ 3 2 a
+ 2 1 b
? 3
? 2
- 2 1
- 3 2
+ 2 1 c
+ 3 2 d
? 5
Output
YES
NO
YES


-----Note-----

In the first query of the third type $k = 3$, we can, for example, choose a sequence $[1, 2, 3]$, since $1 \xrightarrow{\text{a}} 2 \xrightarrow{\text{b}} 3$ and $3 \xrightarrow{\text{a}} 2 \xrightarrow{\text{b}} 1$.

In the second query of the third type $k = 2$, and we can't find sequence $p_1, p_2$ such that arcs $(p_1, p_2)$ and $(p_2, p_1)$ have the same characters.

In the third query of the third type, we can, for example, choose a sequence $[1, 2, 3, 2, 1]$, where $1 \xrightarrow{\text{a}} 2 \xrightarrow{\text{b}} 3 \xrightarrow{\text{d}} 2 \xrightarrow{\text{c}} 1$.

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Vasya is a school PE teacher. Unlike other PE teachers, Vasya doesn't like it when the students stand in line according to their height. Instead, he demands that the children stand in the following order: *a*1,<=*a*2,<=...,<=*a**n*, where *a**i* is the height of the *i*-th student in the line and *n* is the number of students in the line. The children find it hard to keep in mind this strange arrangement, and today they formed the line in the following order: *b*1,<=*b*2,<=...,<=*b**n*, which upset Vasya immensely. Now Vasya wants to rearrange the children so that the resulting order is like this: *a*1,<=*a*2,<=...,<=*a**n*. During each move Vasya can swap two people who stand next to each other in the line. Help Vasya, find the sequence of swaps leading to the arrangement Vasya needs. It is not required to minimize the number of moves.

Input Specification:
The first line contains an integer *n* (1<=≤<=*n*<=≤<=300) which is the number of students. The second line contains *n* space-separated integers *a**i* (1<=≤<=*a**i*<=≤<=109) which represent the height of the student occupying the *i*-th place must possess. The third line contains *n* space-separated integers *b**i* (1<=≤<=*b**i*<=≤<=109) which represent the height of the student occupying the *i*-th place in the initial arrangement. It is possible that some students possess similar heights. It is guaranteed that it is possible to arrange the children in the required order, i.e. *a* and *b* coincide as multisets.

Output Specification:
In the first line print an integer *k* (0<=≤<=*k*<=≤<=106) which is the number of moves. It is not required to minimize *k* but it must not exceed 106. Then print *k* lines each containing two space-separated integers. Line *p**i*, *p**i*<=+<=1 (1<=≤<=*p**i*<=≤<=*n*<=-<=1) means that Vasya should swap students occupying places *p**i* and *p**i*<=+<=1.

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

Demo Output:
['4\n2 3\n1 2\n3 4\n2 3\n', '0\n']

Note:
none

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Alice got an array of length $n$ as a birthday present once again! This is the third year in a row! 

And what is more disappointing, it is overwhelmengly boring, filled entirely with zeros. Bob decided to apply some changes to the array to cheer up Alice.

Bob has chosen $m$ changes of the following form. For some integer numbers $x$ and $d$, he chooses an arbitrary position $i$ ($1 \le i \le n$) and for every $j \in [1, n]$ adds $x + d \cdot dist(i, j)$ to the value of the $j$-th cell. $dist(i, j)$ is the distance between positions $i$ and $j$ (i.e. $dist(i, j) = |i - j|$, where $|x|$ is an absolute value of $x$).

For example, if Alice currently has an array $[2, 1, 2, 2]$ and Bob chooses position $3$ for $x = -1$ and $d = 2$ then the array will become $[2 - 1 + 2 \cdot 2,~1 - 1 + 2 \cdot 1,~2 - 1 + 2 \cdot 0,~2 - 1 + 2 \cdot 1]$ = $[5, 2, 1, 3]$. Note that Bob can't choose position $i$ outside of the array (that is, smaller than $1$ or greater than $n$).

Alice will be the happiest when the elements of the array are as big as possible. Bob claimed that the arithmetic mean value of the elements will work fine as a metric.

What is the maximum arithmetic mean value Bob can achieve?

Input Specification:
The first line contains two integers $n$ and $m$ ($1 \le n, m \le 10^5$) — the number of elements of the array and the number of changes.

Each of the next $m$ lines contains two integers $x_i$ and $d_i$ ($-10^3 \le x_i, d_i \le 10^3$) — the parameters for the $i$-th change.

Output Specification:
Print the maximal average arithmetic mean of the elements Bob can achieve.

Your answer is considered correct if its absolute or relative error doesn't exceed $10^{-6}$.

Demo Input:
['2 3\n-1 3\n0 0\n-1 -4\n', '3 2\n0 2\n5 0\n']

Demo Output:
['-2.500000000000000\n', '7.000000000000000\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Along with some friends you formed the Band of Atonal Percussionists and Cellists. You have been playing for some years together, but you feel unsatisfied with the current level of play. Doing research into some interesting new styles, you are gripped by the intricate details of the world of jazz.

While of course you cannot apply all the new things you have learned immediately, you want to start with improvising some nice new rhythmic figures in the music your band plays. You will play a rhythm where every bar has $n$ beats in it, but then you split up every beat into $m$ notes. In total, you will have $nm$ notes per bar.

Everyone in the band knows that there is no room for squares in jazz. So the number of notes in a bar should be squarefree. That is, there is no number $k > 1$ such that $k^2$ divides the number of notes in a bar.

The percussionist has already suggested a number of beats per bar $n$; now it is up to you to find a number of notes per beat that does not leave any room for squares.

In the second sample we have $n=30$ and $m=7$. This works because $2\leq m < n$ and $m\cdot n = 210$ has no divisor $k^2$ for any $k>1$.

-----Input-----
 - The input is a single squarefree integer $3\leq n\leq 10^5$.

-----Output-----
 - Output an integer $2 \leq m < n$ such that $m \cdot n$ is still squarefree.

If there are multiple possible solutions, you may output any one of them.

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

Sample Input 2:
30
Sample Output 2:
7

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an integer, write an algorithm to convert it to hexadecimal. For negative integer, two’s complement method is used.


Note:

All letters in hexadecimal (a-f) must be in lowercase.
The hexadecimal string must not contain extra leading 0s. If the number is zero, it is represented by a single zero character '0'; otherwise, the first character in the hexadecimal string will not be the zero character.
The given number is guaranteed to fit within the range of a 32-bit signed integer.
You must not use any method provided by the library which converts/formats the number to hex directly.



Example 1:

Input:
26

Output:
"1a"



Example 2:

Input:
-1

Output:
"ffffffff"

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ma5termind likes playing with strings a lot. He thinks that he is so good with strings that nobody can challenge him with a string problem. One fine day, ma5termind's best friend shasha came up with an interesting string problem and decided to challenge him.

Shasha gave him a string S consisting of N lower case letters and an integer Q denoting number of queries to be processed. Each query consists of 2 integers X and Y denoting the indices in the string S. For each query, ma5termind is asked to report the length of longest common prefix between the suffixes starting at position X and position Y.

That day, ma5termind came to know about the truth that he is not good with strings but to show off in front of his friend, he desperately wants to solve this problem. Can you please help him solving this problem ?
Input:
First line will contain two integers N and Q

Next line will contain a string S of length N.

Next Q line will contain two space-seperated integers X and Y.

Ouput:
For each query, print a single integer denoting the length of longest common prefix between the suffixes starting at position X and position Y.
Constraints:

1 ≤ N, Q ≤ 10^5
1 ≤ X, Y ≤ 10^5
S contains only lower case letters

See sample I/O for more clarification.

Scoring:

Subtask 1: 1 ≤ N, Q ≤ 1000 ( 40 pts )
Subtask 2: 1 ≤ N, Q ≤ 10^5 ( 60 pts )

SAMPLE INPUT
12 5
aabbccaabbcc
1 1
1 2
1 7
3 4
3 9

SAMPLE OUTPUT
12
1
6
1
4

Explanation

Q1 : "aabbccaabbcc" is the longest common prefix.
Q2 : "a" is the longest common prefix.
Q3 : "aabbcc" is the longest common prefix.
Q4 : "b" is the longest common prefix.
Q5 : "bbcc" is the longest common prefix.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
DZY loves chessboard, and he enjoys playing with it.

He has a chessboard of n rows and m columns. Some cells of the chessboard are bad, others are good. For every good cell, DZY wants to put a chessman on it. Each chessman is either white or black. After putting all chessmen, DZY wants that no two chessmen with the same color are on two adjacent cells. Two cells are adjacent if and only if they share a common edge.

You task is to find any suitable placement of chessmen on the given chessboard.


-----Input-----

The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 100).

Each of the next n lines contains a string of m characters: the j-th character of the i-th string is either "." or "-". A "." means that the corresponding cell (in the i-th row and the j-th column) is good, while a "-" means it is bad.


-----Output-----

Output must contain n lines, each line must contain a string of m characters. The j-th character of the i-th string should be either "W", "B" or "-". Character "W" means the chessman on the cell is white, "B" means it is black, "-" means the cell is a bad cell.

If multiple answers exist, print any of them. It is guaranteed that at least one answer exists.


-----Examples-----
Input
1 1
.

Output
B

Input
2 2
..
..

Output
BW
WB

Input
3 3
.-.
---
--.
Output
B-B
---
--B


-----Note-----

In the first sample, DZY puts a single black chessman. Of course putting a white one is also OK.

In the second sample, all 4 cells are good. No two same chessmen share an edge in the sample output.

In the third sample, no good cells are adjacent. So you can just put 3 chessmen, no matter what their colors are.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have to write two methods to *encrypt* and *decrypt* strings.
Both methods have two parameters:
```
1. The string to encrypt/decrypt
2. The Qwerty-Encryption-Key (000-999) 
```

The rules are very easy:
```
The crypting-regions are these 3 lines from your keyboard:
1. "qwertyuiop"
2. "asdfghjkl"
3. "zxcvbnm,."

If a char of the string is not in any of these regions, take the char direct in the output.
If a char of the string is in one of these regions: Move it by the part of the key in the 
region and take this char at the position from the region. 
If the movement is over the length of the region, continue at the beginning.
The encrypted char must have the same case like the decrypted char! 
So for upperCase-chars the regions are the same, but with pressed "SHIFT"!

The Encryption-Key is an integer number from 000 to 999. E.g.: 127

The first digit of the key (e.g. 1) is the movement for the first line.
The second digit of the key (e.g. 2) is the movement for the second line.
The third digit of the key (e.g. 7) is the movement for the third line.

(Consider that the key is an integer! When you got a 0 this would mean 000. A 1 would mean 001. And so on.)
```

You do not need to do any prechecks. The strings will always be not null 
and will always have a length > 0. You do not have to throw any exceptions.

An Example:
```
Encrypt "Ball" with key 134
1. "B" is in the third region line. Move per 4 places in the region. -> ">" (Also "upperCase"!)
2. "a" is in the second region line. Move per 3 places in the region. -> "f"
3. "l" is in the second region line. Move per 3 places in the region. -> "d"
4. "l" is in the second region line. Move per 3 places in the region. -> "d"
--> Output would be ">fdd"
```

*Hint: Don't forget: The regions are from an US-Keyboard!*
*In doubt google for "US Keyboard."*



This kata is part of the Simple Encryption Series:
Simple Encryption #1 - Alternating Split
Simple Encryption #2 - Index-Difference
Simple Encryption #3 - Turn The Bits Around
Simple Encryption #4 - Qwerty

Have fun coding it and please don't forget to vote and rank this kata! :-)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:

Input:nums = [1,1,1], k = 2
Output: 2



Note:

The length of the array is in range [1, 20,000].
The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The chef is trying to solve some pattern problems, Chef wants your help to code it. Chef has one number K to form a new pattern. Help the chef to code this pattern problem.

-----Input:-----
- First-line will contain $T$, the number of test cases. Then the test cases follow. 
- Each test case contains a single line of input, one integer $K$. 

-----Output:-----
For each test case, output as the pattern.

-----Constraints-----
- $1 \leq T \leq 50$
- $1 \leq K \leq 50$

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

-----Sample Output:-----
1
1
23
1
23
456
1
23
4 5
6789
1
23
4 5
6  7
89101112

-----EXPLANATION:-----
No need, else pattern can be decode easily.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Konrad is a Human Relations consultant working for VoltModder, a large electrical equipment producer. Today, he has been tasked with evaluating the level of happiness in the company.

There are $n$ people working for VoltModder, numbered from $1$ to $n$. Each employee earns a different amount of money in the company — initially, the $i$-th person earns $i$ rubles per day.

On each of $q$ following days, the salaries will be revised. At the end of the $i$-th day, employee $v_i$ will start earning $n+i$ rubles per day and will become the best-paid person in the company. The employee will keep his new salary until it gets revised again.

Some pairs of people don't like each other. This creates a great psychological danger in the company. Formally, if two people $a$ and $b$ dislike each other and $a$ earns more money than $b$, employee $a$ will brag about this to $b$. A dangerous triple is a triple of three employees $a$, $b$ and $c$, such that $a$ brags to $b$, who in turn brags to $c$. If $a$ dislikes $b$, then $b$ dislikes $a$.

At the beginning of each day, Konrad needs to evaluate the number of dangerous triples in the company. Can you help him do it?


-----Input-----

The first line contains two integers $n$ and $m$ ($1 \le n \le 100\,000$, $0 \le m \le 100\,000$) — the number of employees in the company and the number of pairs of people who don't like each other. Each of the following $m$ lines contains two integers $a_i$, $b_i$ ($1 \le a_i, b_i \le n$, $a_i \neq b_i$) denoting that employees $a_i$ and $b_i$ hate each other (that is, $a_i$ dislikes $b_i$ and $b_i$ dislikes $a_i$). Each such relationship will be mentioned exactly once.

The next line contains an integer $q$ ($0 \le q \le 100\,000$) — the number of salary revisions. The $i$-th of the following $q$ lines contains a single integer $v_i$ ($1 \le v_i \le n$) denoting that at the end of the $i$-th day, employee $v_i$ will earn the most.


-----Output-----

Output $q + 1$ integers. The $i$-th of them should contain the number of dangerous triples in the company at the beginning of the $i$-th day.


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

Output
4
3
2

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

Output
1
1
1
1
1
1



-----Note-----

Consider the first sample test. The $i$-th row in the following image shows the structure of the company at the beginning of the $i$-th day. A directed edge from $a$ to $b$ denotes that employee $a$ brags to employee $b$. The dangerous triples are marked by highlighted edges. [Image]

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Little Petya very much likes computers. Recently he has received a new "Ternatron IV" as a gift from his mother. Unlike other modern computers, "Ternatron IV" operates with ternary and not binary logic. Petya immediately wondered how the *xor* operation is performed on this computer (and whether there is anything like it).

It turned out that the operation does exist (however, it is called *tor*) and it works like this. Suppose that we need to calculate the value of the expression *a* *tor* *b*. Both numbers *a* and *b* are written in the ternary notation one under the other one (*b* under *a*). If they have a different number of digits, then leading zeroes are added to the shorter number until the lengths are the same. Then the numbers are summed together digit by digit. The result of summing each two digits is calculated modulo 3. Note that there is no carry between digits (i. e. during this operation the digits aren't transferred). For example: 1410 *tor* 5010<==<=01123 *tor* 12123<==<=10213<==<=3410.

Petya wrote numbers *a* and *c* on a piece of paper. Help him find such number *b*, that *a* *tor* *b*<==<=*c*. If there are several such numbers, print the smallest one.

Input Specification:
The first line contains two integers *a* and *c* (0<=≤<=*a*,<=*c*<=≤<=109). Both numbers are written in decimal notation.

Output Specification:
Print the single integer *b*, such that *a* *tor* *b*<==<=*c*. If there are several possible numbers *b*, print the smallest one. You should print the number in decimal notation.

Demo Input:
['14 34\n', '50 34\n', '387420489 225159023\n', '5 5\n']

Demo Output:
['50\n', '14\n', '1000000001\n', '0\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We'll call a set of positive integers a beautiful if the following condition fulfills: for any prime p, if <image>, then <image>. In other words, if one number from the set is divisible by prime p, then at least half of numbers from the set is divisible by p.

Your task is to find any beautiful set, where the number of elements is equal to k and each element doesn't exceed 2k2.

Input

The first line contains integer k (10 ≤ k ≤ 5000) that shows how many numbers the required beautiful set should have.

Output

In the first line print k space-separated integers that are a beautiful set. If there are multiple such sets, you are allowed to print any of them.

Examples

Input

10


Output

16 18 24 27 36 48 54 72 108 144 

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

Time Limit: 2 seconds

Memory Limit: 64 megabytes

Problem Description:
A group of tourists is going to kayak and catamaran tour. A rented lorry has arrived to the boat depot to take kayaks and catamarans to the point of departure. It's known that all kayaks are of the same size (and each of them occupies the space of 1 cubic metre), and all catamarans are of the same size, but two times bigger than kayaks (and occupy the space of 2 cubic metres).

Each waterborne vehicle has a particular carrying capacity, and it should be noted that waterborne vehicles that look the same can have different carrying capacities. Knowing the truck body volume and the list of waterborne vehicles in the boat depot (for each one its type and carrying capacity are known), find out such set of vehicles that can be taken in the lorry, and that has the maximum total carrying capacity. The truck body volume of the lorry can be used effectively, that is to say you can always put into the lorry a waterborne vehicle that occupies the space not exceeding the free space left in the truck body.

Input Specification:
The first line contains a pair of integer numbers *n* and *v* (1<=≤<=*n*<=≤<=105; 1<=≤<=*v*<=≤<=109), where *n* is the number of waterborne vehicles in the boat depot, and *v* is the truck body volume of the lorry in cubic metres. The following *n* lines contain the information about the waterborne vehicles, that is a pair of numbers *t**i*,<=*p**i* (1<=≤<=*t**i*<=≤<=2; 1<=≤<=*p**i*<=≤<=104), where *t**i* is the vehicle type (1 – a kayak, 2 – a catamaran), and *p**i* is its carrying capacity. The waterborne vehicles are enumerated in order of their appearance in the input file.

Output Specification:
In the first line print the maximum possible carrying capacity of the set. In the second line print a string consisting of the numbers of the vehicles that make the optimal set. If the answer is not unique, print any of them.

Demo Input:
['3 2\n1 2\n2 7\n1 3\n']

Demo Output:
['7\n2\n']

Note:
none

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