vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You are given an HTML code snippet of $N$ lines.
 Your task is to detect and print all the HTML tags, attributes and attribute values.

Print the detected items in the following format:

Tag1
Tag2
-> Attribute2[0] > Attribute_value2[0]
-> Attribute2[1] > Attribute_value2[1]
-> Attribute2[2] > Attribute_value2[2]
Tag3
-> Attribute3[0] > Attribute_value3[0]

The -> symbol indicates that the tag contains an attribute. It is immediately followed by the name of the attribute and the attribute value. 

The > symbol acts as a separator of attributes and attribute values.

If an HTML tag has no attribute then simply print the name of the tag.

Note: Do not detect any HTML tag, attribute or attribute value inside the HTML comment tags (<!-- Comments -->). Comments can be multiline.

All attributes have an attribute value.

Input Format

The first line contains an integer $N$, the number of lines in the HTML code snippet.

The next $N$ lines contain HTML code.

Constraints

$0<N<100$

Output Format

Print the HTML tags, attributes and attribute values in order of their occurrence from top to bottom in the snippet.

Format your answers as explained in the problem statement.

Sample Input
9
<head>
<title>HTML</title>
</head>
<object type="application/x-flash" 
  data="your-file.swf" 
  width="0" height="0">
  <!-- <param name="movie" value="your-file.swf" /> -->
  <param name="quality" value="high"/>
</object>

Sample Output
head
title
object
-> type > application/x-flash
-> data > your-file.swf
-> width > 0
-> height > 0
param
-> name > quality
-> value > high

Explanation

head tag: Print the head tag only because it has no attribute.

title tag: Print the title tag only because it has no attribute.

object tag: Print the object tag. In the next $\begin{array}{c}A\end{array}$ lines, print the attributes type, data, width and                     height along with their respective values.

<!-- Comment  --> tag: Don't detect anything inside it.

param tag: Print the param tag. In the next $2$ lines, print the attributes name along with                     their respective values.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Eugeny has array *a*<==<=*a*1,<=*a*2,<=...,<=*a**n*, consisting of *n* integers. Each integer *a**i* equals to -1, or to 1. Also, he has *m* queries:
 -  Query number *i* is given as a pair of integers *l**i*, *r**i* (1<=≤<=*l**i*<=≤<=*r**i*<=≤<=*n*). -  The response to the query will be integer 1, if the elements of array *a* can be rearranged so as the sum *a**l**i*<=+<=*a**l**i*<=+<=1<=+<=...<=+<=*a**r**i*<==<=0, otherwise the response to the query will be integer 0. 
Help Eugeny, answer all his queries.

Input Specification:
The first line contains integers *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=2·105). The second line contains *n* integers *a*1,<=*a*2,<=...,<=*a**n* (*a**i*<==<=-1,<=1). Next *m* lines contain Eugene's queries. The *i*-th line contains integers *l**i*,<=*r**i* (1<=≤<=*l**i*<=≤<=*r**i*<=≤<=*n*).

Output Specification:
Print *m* integers — the responses to Eugene's queries in the order they occur in the input.

Demo Input:
['2 3\n1 -1\n1 1\n1 2\n2 2\n', '5 5\n-1 1 1 1 -1\n1 1\n2 3\n3 5\n2 5\n1 5\n']

Demo Output:
['0\n1\n0\n', '0\n1\n0\n1\n0\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Tokitsukaze and CSL are playing a little game of stones.

In the beginning, there are $n$ piles of stones, the $i$-th pile of which has $a_i$ stones. The two players take turns making moves. Tokitsukaze moves first. On each turn the player chooses a nonempty pile and removes exactly one stone from the pile. A player loses if all of the piles are empty before his turn, or if after removing the stone, two piles (possibly empty) contain the same number of stones. Supposing that both players play optimally, who will win the game?

Consider an example: $n=3$ and sizes of piles are $a_1=2$, $a_2=3$, $a_3=0$. It is impossible to choose the empty pile, so Tokitsukaze has two choices: the first and the second piles. If she chooses the first pile then the state will be $[1, 3, 0]$ and it is a good move. But if she chooses the second pile then the state will be $[2, 2, 0]$ and she immediately loses. So the only good move for her is to choose the first pile. 

Supposing that both players always take their best moves and never make mistakes, who will win the game?

Note that even if there are two piles with the same number of stones at the beginning, Tokitsukaze may still be able to make a valid first move. It is only necessary that there are no two piles with the same number of stones after she moves.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 10^5$) — the number of piles.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_1, a_2, \ldots, a_n \le 10^9$), which mean the $i$-th pile has $a_i$ stones.


-----Output-----

Print "sjfnb" (without quotes) if Tokitsukaze will win, or "cslnb" (without quotes) if CSL will win. Note the output characters are case-sensitive.


-----Examples-----
Input
1
0

Output
cslnb

Input
2
1 0

Output
cslnb

Input
2
2 2

Output
sjfnb

Input
3
2 3 1

Output
sjfnb



-----Note-----

In the first example, Tokitsukaze cannot take any stone, so CSL will win.

In the second example, Tokitsukaze can only take a stone from the first pile, and then, even though they have no stone, these two piles will have the same number of stones, which implies CSL will win.

In the third example, Tokitsukaze will win. Here is one of the optimal ways:

  Firstly, Tokitsukaze can choose the first pile and take a stone from that pile.  Then, CSL can only choose the first pile, because if he chooses the second pile, he will lose immediately.  Finally, Tokitsukaze can choose the second pile, and then CSL will have no choice but to lose. 

In the fourth example, they only have one good choice at any time, so Tokitsukaze can make the game lasting as long as possible and finally win.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array nums of integers, we need to find the maximum possible sum of elements of the array such that it is divisible by three.


 
Example 1:
Input: nums = [3,6,5,1,8]
Output: 18
Explanation: Pick numbers 3, 6, 1 and 8 their sum is 18 (maximum sum divisible by 3).
Example 2:
Input: nums = [4]
Output: 0
Explanation: Since 4 is not divisible by 3, do not pick any number.

Example 3:
Input: nums = [1,2,3,4,4]
Output: 12
Explanation: Pick numbers 1, 3, 4 and 4 their sum is 12 (maximum sum divisible by 3).

 
Constraints:

1 <= nums.length <= 4 * 10^4
1 <= nums[i] <= 10^4

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

The task is described in the title: find the sum of all numbers with the same digits(permutations) **including** duplicates. However, due to the fact that this is a performance edition kata, `num` can go up to `10**10000`. That's a number with 10001 digits(at most). Be sure to use efficient algorithms and good luck! All numbers tested for will be positive.

**Examples**
```
sum_arrangements(98) returns 89+98 = 187
sum_arrangements(123) returns 1332 #123 + 132 + 213 + 231 + 312 + 321 = 1332
sum_arrangements(1185) returns 99990 #1185 + 1158 + 1815 + 1851 + 1518 + 1581 + 1185 + 1158 + 1815 + 1851 + 1518 + 1581 + 8115 + 8151 + 8115 + 8151 + 8511 + 8511 + 5118 + 5181 + 5118 + 5181 + 5811 + 5811 = 99990
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
An array, $\mbox{A}$, is defined as follows: 

$A_0=0$
$A_x=A_{x-1}\oplus x$ for $x>0$, where $\oplus$ is the symbol for XOR

You will be given a left and right index $\mbox{l r}$.  You must determine the XOR sum of the segment of $\mbox{A}$ as $A[l]\oplus A[l+1]\oplus ...\oplus A[r-1]\oplus A[r]$. 

For example, $A=[0,1,3,0,4,1,7,0,8]$.  The segment from $l=1$ to $r=4$ sums to $1\oplus3\oplus0\oplus4=6$. 

Print the answer to each question.

Function Description  

Complete the xorSequence function in the editor below.  It should return the integer value calculated.  

xorSequence has the following parameter(s):  

l: the lower index of the range to sum  
r: the higher index of the range to sum  

Input Format

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

Each of the next $\textit{q}$ lines contains two space-separated integers, $l\left[i\right]$ and $r[i]$, the inclusive left and right indexes of the segment to query.

Constraints

$1\leq q\leq10^5$ 

 $1\leq l[i]\leq r[i]\leq10^{15}$  

Output Format

On a new line for each test case, print the XOR-Sum of $\mbox{A}$'s elements in the inclusive range between indices $l\left[i\right]$ and $r[i]$.

Sample Input 0
3
2 4
2 8
5 9

Sample Output 0
7
9
15

Explanation 0

The beginning of our array looks like this:
 $A=[0,1,3,0,4,1,7,0,8,1,11,...]$

Test Case 0: 

$3\oplus0\oplus4=7$

Test Case 1: 

$3\oplus0\oplus4\oplus1\oplus7\oplus0\oplus8=9$

Test Case 2: 

$1\oplus7\oplus0\oplus8\oplus1=15$

Sample Input 1
3
3 5
4 6
15 20

Sample Output 1
5
2
22

Explanation 1

$A=[0,1,3,0,4,1,7,0,8,1,11,0,12,1,15,0,16,1,19,0,20,1,23,0,24,1,...]$.  Perform the xor sum on each interval: 

$3-5:0\oplus4\oplus1=5$ 

$4-6:4\oplus1\oplus7=2$ 

$15-20:0\oplus16\oplus1\oplus19\oplus0\oplus20=22$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Amr loves Geometry. One day he came up with a very interesting problem.

Amr has a circle of radius r and center in point (x, y). He wants the circle center to be in new position (x', y').

In one step Amr can put a pin to the border of the circle in a certain point, then rotate the circle around that pin by any angle and finally remove the pin.

Help Amr to achieve his goal in minimum number of steps.


-----Input-----

Input consists of 5 space-separated integers r, x, y, x' y' (1 ≤ r ≤ 10^5,  - 10^5 ≤ x, y, x', y' ≤ 10^5), circle radius, coordinates of original center of the circle and coordinates of destination center of the circle respectively.


-----Output-----

Output a single integer — minimum number of steps required to move the center of the circle to the destination point.


-----Examples-----
Input
2 0 0 0 4

Output
1

Input
1 1 1 4 4

Output
3

Input
4 5 6 5 6

Output
0



-----Note-----

In the first sample test the optimal way is to put a pin at point (0, 2) and rotate the circle by 180 degrees counter-clockwise (or clockwise, no matter).

[Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chessboard is a board of n × n squares arranged in two alternating colors (black and white). Top left square is white. You are given board size n. Output an image of a chessboard, with black and white squares marked with '#' and '.' characters, respectively.

Input

The only line of input contains an integer n (1 ≤ n ≤ 9).

Output

Output an image of n × n chessboard.

Examples

Input

4


Output

.#.#
#.#.
.#.#
#.#.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
One popular website developed an unusual username editing procedure. One can change the username only by deleting some characters from it: to change the current name *s*, a user can pick number *p* and character *c* and delete the *p*-th occurrence of character *c* from the name. After the user changed his name, he can't undo the change.

For example, one can change name "arca" by removing the second occurrence of character "a" to get "arc". 

Polycarpus learned that some user initially registered under nickname *t*, where *t* is a concatenation of *k* copies of string *s*. Also, Polycarpus knows the sequence of this user's name changes. Help Polycarpus figure out the user's final name.

Input Specification:
The first line contains an integer *k* (1<=≤<=*k*<=≤<=2000). The second line contains a non-empty string *s*, consisting of lowercase Latin letters, at most 100 characters long. The third line contains an integer *n* (0<=≤<=*n*<=≤<=20000) — the number of username changes. Each of the next *n* lines contains the actual changes, one per line. The changes are written as "*p**i* *c**i*" (without the quotes), where *p**i* (1<=≤<=*p**i*<=≤<=200000) is the number of occurrences of letter *c**i*, *c**i* is a lowercase Latin letter. It is guaranteed that the operations are correct, that is, the letter to be deleted always exists, and after all operations not all letters are deleted from the name. The letters' occurrences are numbered starting from 1.

Output Specification:
Print a single string — the user's final name after all changes are applied to it.

Demo Input:
['2\nbac\n3\n2 a\n1 b\n2 c\n', '1\nabacaba\n4\n1 a\n1 a\n1 c\n2 b\n']

Demo Output:
['acb\n', 'baa\n']

Note:
Let's consider the first sample. Initially we have name "bacbac"; the first operation transforms it into "bacbc", the second one — to "acbc", and finally, the third one transforms it into "acb".

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Since Sonya is interested in robotics too, she decided to construct robots that will read and recognize numbers.

Sonya has drawn $n$ numbers in a row, $a_i$ is located in the $i$-th position. She also has put a robot at each end of the row (to the left of the first number and to the right of the last number). Sonya will give a number to each robot (they can be either same or different) and run them. When a robot is running, it is moving toward to another robot, reading numbers in the row. When a robot is reading a number that is equal to the number that was given to that robot, it will turn off and stay in the same position.

Sonya does not want robots to break, so she will give such numbers that robots will stop before they meet. That is, the girl wants them to stop at different positions so that the first robot is to the left of the second one.

For example, if the numbers $[1, 5, 4, 1, 3]$ are written, and Sonya gives the number $1$ to the first robot and the number $4$ to the second one, the first robot will stop in the $1$-st position while the second one in the $3$-rd position. In that case, robots will not meet each other. As a result, robots will not be broken. But if Sonya gives the number $4$ to the first robot and the number $5$ to the second one, they will meet since the first robot will stop in the $3$-rd position while the second one is in the $2$-nd position.

Sonya understands that it does not make sense to give a number that is not written in the row because a robot will not find this number and will meet the other robot.

Sonya is now interested in finding the number of different pairs that she can give to robots so that they will not meet. In other words, she wants to know the number of pairs ($p$, $q$), where she will give $p$ to the first robot and $q$ to the second one. Pairs ($p_i$, $q_i$) and ($p_j$, $q_j$) are different if $p_i\neq p_j$ or $q_i\neq q_j$.

Unfortunately, Sonya is busy fixing robots that broke after a failed launch. That is why she is asking you to find the number of pairs that she can give to robots so that they will not meet.

Input Specification:
The first line contains a single integer $n$ ($1\leq n\leq 10^5$) — the number of numbers in a row.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1\leq a_i\leq 10^5$) — the numbers in a row.

Output Specification:
Print one number — the number of possible pairs that Sonya can give to robots so that they will not meet.

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

Demo Output:
['9\n', '7\n']

Note:
In the first example, Sonya can give pairs ($1$, $1$), ($1$, $3$), ($1$, $4$), ($1$, $5$), ($4$, $1$), ($4$, $3$), ($5$, $1$), ($5$, $3$), and ($5$, $4$).

In the second example, Sonya can give pairs ($1$, $1$), ($1$, $2$), ($1$, $3$), ($2$, $1$), ($2$, $2$), ($2$, $3$), and ($3$, $2$).

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

Given an array X of positive integers, its elements are to be transformed by running the following operation on them as many times as required:

```if X[i] > X[j] then X[i] = X[i] - X[j]```

When no more transformations are possible, return its sum ("smallest possible sum").

For instance, the successive transformation of the elements of input X = [6, 9, 21] is detailed below:
```
X_1 = [6, 9, 12] # -> X_1[2] = X[2] - X[1] = 21 - 9
X_2 = [6, 9, 6]  # -> X_2[2] = X_1[2] - X_1[0] = 12 - 6
X_3 = [6, 3, 6]  # -> X_3[1] = X_2[1] - X_2[0] = 9 - 6
X_4 = [6, 3, 3]  # -> X_4[2] = X_3[2] - X_3[1] = 6 - 3
X_5 = [3, 3, 3]  # -> X_5[1] = X_4[0] - X_4[1] = 6 - 3
```
The returning output is the sum of the final transformation (here 9).

## Example

## Solution steps:

## Additional notes:

There are performance tests consisted of very big numbers and arrays of size at least 30000. Please write an efficient algorithm to prevent timeout.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Dhote and Shweta went on a tour by plane for the first time.Dhote was surprised by the conveyor belt  at the airport.As Shweta was getting bored Dhote had an idea of playing a game with her.He asked Shweta to count the number of bags whose individual weight is greater than or equal to the half of the total number of bags on the conveyor belt.Shweta got stuck in the puzzle! Help Shweta. 

-----Input:-----
- First line will contain T$T$, number of testcases. Then the testcases follow. 
- Each testcase contains of a single line of input, one  integers N$N$.
- next line conatins N$N$ integers that represents weight of bag 

-----Output:-----
For each testcase, print required answer in new line .

-----Constraints-----
- 1≤T≤1000$1 \leq T \leq 1000$
- 1≤N≤105$1 \leq N \leq 10^5$
- 1≤weightofbag≤105$ 1\leq  weight of bag   \leq 10^5$ 

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

-----Sample Output:-----
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let $n$ be an integer. Consider all permutations on integers $1$ to $n$ in lexicographic order, and concatenate them into one big sequence $p$. For example, if $n = 3$, then $p = [1, 2, 3, 1, 3, 2, 2, 1, 3, 2, 3, 1, 3, 1, 2, 3, 2, 1]$. The length of this sequence will be $n \cdot n!$.

Let $1 \leq i \leq j \leq n \cdot n!$ be a pair of indices. We call the sequence $(p_i, p_{i+1}, \dots, p_{j-1}, p_j)$ a subarray of $p$. Its length is defined as the number of its elements, i.e., $j - i + 1$. Its sum is the sum of all its elements, i.e., $\sum_{k=i}^j p_k$. 

You are given $n$. Find the number of subarrays of $p$ of length $n$ having sum $\frac{n(n+1)}{2}$. Since this number may be large, output it modulo $998244353$ (a prime number). 


-----Input-----

The only line contains one integer $n$ ($1 \leq n \leq 10^6$), as described in the problem statement.


-----Output-----

Output a single integer — the number of subarrays of length $n$ having sum $\frac{n(n+1)}{2}$, modulo $998244353$.


-----Examples-----
Input
3

Output
9

Input
4

Output
56

Input
10

Output
30052700



-----Note-----

In the first sample, there are $16$ subarrays of length $3$. In order of appearance, they are:

$[1, 2, 3]$, $[2, 3, 1]$, $[3, 1, 3]$, $[1, 3, 2]$, $[3, 2, 2]$, $[2, 2, 1]$, $[2, 1, 3]$, $[1, 3, 2]$, $[3, 2, 3]$, $[2, 3, 1]$, $[3, 1, 3]$, $[1, 3, 1]$, $[3, 1, 2]$, $[1, 2, 3]$, $[2, 3, 2]$, $[3, 2, 1]$. 

Their sums are $6$, $6$, $7$, $6$, $7$, $5$, $6$, $6$, $8$, $6$, $7$, $5$, $6$, $6$, $7$, $6$. As $\frac{n(n+1)}{2} = 6$, the answer is $9$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One day Bob got a letter in an envelope. Bob knows that when Berland's post officers send a letter directly from city «A» to city «B», they stamp it with «A B», or «B A». Unfortunately, often it is impossible to send a letter directly from the city of the sender to the city of the receiver, that's why the letter is sent via some intermediate cities. Post officers never send a letter in such a way that the route of this letter contains some city more than once. Bob is sure that the post officers stamp the letters accurately.

There are n stamps on the envelope of Bob's letter. He understands that the possible routes of this letter are only two. But the stamps are numerous, and Bob can't determine himself none of these routes. That's why he asks you to help him. Find one of the possible routes of the letter.

Input

The first line contains integer n (1 ≤ n ≤ 105) — amount of mail stamps on the envelope. Then there follow n lines with two integers each — description of the stamps. Each stamp is described with indexes of the cities between which a letter is sent. The indexes of cities are integers from 1 to 109. Indexes of all the cities are different. Every time the letter is sent from one city to another, exactly one stamp is put on the envelope. It is guaranteed that the given stamps correspond to some valid route from some city to some other city. 

Output

Output n + 1 numbers — indexes of cities in one of the two possible routes of the letter.

Examples

Input

2
1 100
100 2


Output

2 100 1 

Input

3
3 1
100 2
3 2


Output

100 2 3 1 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
On each of the following $N$ days (numbered $1$ through $N$), Chef is planning to cook either pizza or broccoli. He wrote down a string $A$ with length $N$, where for each valid $i$, if the character $A_i$ is '1', then he will cook pizza on the $i$-th day, while if $A_i$ is '0', he will cook broccoli on this day.
Chefu, his son, loves pizza but hates broccoli ― just like most kids. He wants to select a substring of $A$ with length $K$ and change each character '0' in this substring to '1'. Afterwards, let's define pizza time as the maximum number of consecutive days where Chef will cook pizza. Find the maximum pizza time Chefu can achieve.

-----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 $N$ and $K$. 
- The second line contains a string $A$ with length $N$.

-----Output-----
For each test case, print a single line containing one integer ― the maximum pizza time.

-----Constraints-----
- $1 \le T \le 1,000$
- $1 \le K \le N \le 10^5$
- $A$ contains only characters '0' and '1'
- the sum of $N$ over all test cases does not exceed $10^6$

-----Subtasks-----
Subtask #1 (50 points):
- $N \le 10^3$
- the sum of $N$ over all test cases does not exceed $10^4$
Subtask #2 (50 points): original constraints

-----Example Input-----
2
13 2
0101110000101
6 3
100001

-----Example Output-----
5
4

-----Explanation-----
Example case 1: Chefu can choose the substring $A[2, 3]$ = "10", and change the third character of $A$ to '1'. Then, the pizza time is $5$ days: from day $2$ to day $6$.
Example case 2: Chefu can choose the substring $A[2, 4]$ = "000". Then, the pizza time is $4$ days: from day $1$ to day $4$.

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

The only line of the input contains a 7-digit hexadecimal number. The first "digit" of the number is letter A, the rest of the "digits" are decimal digits 0-9.

Output

Output a single integer.

Examples

Input


A278832


Output


0


Input


A089956


Output


0


Input


A089957


Output


1


Input


A144045


Output


1

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