vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
A certain business maintains a list of all its customers' names. The list is arranged in order of importance, with the last customer in the list being the most important. Now, he want to create a new list sorted alphabetically according to customers' last names, but among customers with the same last name he want the more important ones to appear earlier in the new list. Alphabetical order (and equality of last names) should not be case sensitive.

Input:-
First line contains no. of test cases and first line of each test case contains n i.e. no. of elements and next n lines contains contains a name.

Output:- Print the new list with each element in a new line.

SAMPLE INPUT
2
5
Tom Jones
ADAMS
BOB ADAMS
Tom Jones
STEVE jONeS
3
Trudy
Trudy
TRUDY

SAMPLE OUTPUT
BOB ADAMS
ADAMS
STEVE jONeS
Tom Jones
Tom Jones
TRUDY
Trudy
Trudy

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sparsh(techno-cultural fest of SVNIT) fever is spread all over SVNIT and now the core-committee of Sparsh wants to propagate it all over the state. The publicity team is planning to fill the nearby places with giant rectangular hoardings. For placing a hoarding they've been given a frame in shape of a grid.

The frame is made up of M rods placed horizontally one above the other and N rods placed vertically on top of the horizontal rods thereby forming a grid. The smallest rectangle formed is a square of unit area.

Now after a while, they are informed only the area of hoarding  (A units) but there isn't any information on it's dimensions. It is also known that the hoarding will be rectangular in shape with integral edge length. 

Now your task is to find how many rectangular frames of different dimensions are possible with area A units in the given grid.
Input:
First line contains single integer denoting number of test cases T.
T lines follows.
Each line contains 3 integers M,N,A.
M,N are two different sizes of rods.
A is area of hoarding.  

Output:
Print single integral answer for each test case in separate lines.

Constraints:
SubTask1:
1 ≤ T ≤ 2500
2 ≤ M,N ≤ 100000
1 ≤ A ≤ (m-1)*(n-1)  

SubTask2: 
1 ≤ T ≤ 25
2 ≤ M,N ≤ 10000000
1 ≤ A ≤ (m-1)*(n-1)  

Problem Setter : Prashant Arya

SAMPLE INPUT
2
2 2 1
4 5 6

SAMPLE OUTPUT
1
7

Explanation

Case 2 : 4 5 6
With the given rods, a grid of 3x4 dimensions can be formed. Now from this, there are 4 different 2x3, and 3 different 3x2 rectangles possible. Thus answer is 7.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have an array $a_1, a_2, \dots, a_n$. 

Let's call some subarray $a_l, a_{l + 1}, \dots , a_r$ of this array a subpermutation if it contains all integers from $1$ to $r-l+1$ exactly once. For example, array $a = [2, 2, 1, 3, 2, 3, 1]$ contains $6$ subarrays which are subpermutations: $[a_2 \dots a_3]$, $[a_2 \dots a_4]$, $[a_3 \dots a_3]$, $[a_3 \dots a_5]$, $[a_5 \dots a_7]$, $[a_7 \dots a_7]$.

You are asked to calculate the number of subpermutations.


-----Input-----

The first line contains one integer $n$ ($1 \le n \le 3 \cdot 10^5$).

The second line contains $n$ integers $a_1, a_2, \dots , a_n$ ($1 \le a_i \le n$). 

This array can contain the same integers.


-----Output-----

Print the number of subpermutations of the array $a$.


-----Examples-----
Input
8
2 4 1 3 4 2 1 2

Output
7

Input
5
1 1 2 1 2

Output
6



-----Note-----

There are $7$ subpermutations in the first test case. Their segments of indices are $[1, 4]$, $[3, 3]$, $[3, 6]$, $[4, 7]$, $[6, 7]$, $[7, 7]$ and $[7, 8]$.

In the second test case $6$ subpermutations exist: $[1, 1]$, $[2, 2]$, $[2, 3]$, $[3, 4]$, $[4, 4]$ and $[4, 5]$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Zookeeper is buying a carton of fruit to feed his pet wabbit. The fruits are a sequence of apples and oranges, which is represented by a binary string $s_1s_2\ldots s_n$ of length $n$. $1$ represents an apple and $0$ represents an orange.

Since wabbit is allergic to eating oranges, Zookeeper would like to find the longest contiguous sequence of apples. Let $f(l,r)$ be the longest contiguous sequence of apples in the substring $s_{l}s_{l+1}\ldots s_{r}$. 

Help Zookeeper find $\sum_{l=1}^{n} \sum_{r=l}^{n} f(l,r)$, or the sum of $f$ across all substrings.


-----Input-----

The first line contains a single integer $n$ $(1 \leq n \leq 5 \cdot 10^5)$.

 The next line contains a binary string $s$ of length $n$ $(s_i \in \{0,1\})$ 


-----Output-----

Print a single integer: $\sum_{l=1}^{n} \sum_{r=l}^{n} f(l,r)$. 


-----Examples-----
Input
4
0110

Output
12

Input
7
1101001

Output
30

Input
12
011100011100

Output
156



-----Note-----

In the first test, there are ten substrings. The list of them (we let $[l,r]$ be the substring $s_l s_{l+1} \ldots s_r$):  $[1,1]$: 0  $[1,2]$: 01  $[1,3]$: 011  $[1,4]$: 0110  $[2,2]$: 1  $[2,3]$: 11  $[2,4]$: 110  $[3,3]$: 1  $[3,4]$: 10  $[4,4]$: 0 

The lengths of the longest contiguous sequence of ones in each of these ten substrings are $0,1,2,2,1,2,2,1,1,0$ respectively. Hence, the answer is $0+1+2+2+1+2+2+1+1+0 = 12$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little Chris knows there's no fun in playing dominoes, he thinks it's too random and doesn't require skill. Instead, he decided to play with the dominoes and make a "domino show".

Chris arranges n dominoes in a line, placing each piece vertically upright. In the beginning, he simultaneously pushes some of the dominoes either to the left or to the right. However, somewhere between every two dominoes pushed in the same direction there is at least one domino pushed in the opposite direction.

After each second, each domino that is falling to the left pushes the adjacent domino on the left. Similarly, the dominoes falling to the right push their adjacent dominoes standing on the right. When a vertical domino has dominoes falling on it from both sides, it stays still due to the balance of the forces. The figure shows one possible example of the process. [Image] 

Given the initial directions Chris has pushed the dominoes, find the number of the dominoes left standing vertically at the end of the process!


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 3000), the number of the dominoes in the line. The next line contains a character string s of length n. The i-th character of the string s_{i} is equal to   "L", if the i-th domino has been pushed to the left;  "R", if the i-th domino has been pushed to the right;  ".", if the i-th domino has not been pushed. 

It is guaranteed that if s_{i} = s_{j} = "L" and i < j, then there exists such k that i < k < j and s_{k} = "R"; if s_{i} = s_{j} = "R" and i < j, then there exists such k that i < k < j and s_{k} = "L".


-----Output-----

Output a single integer, the number of the dominoes that remain vertical at the end of the process.


-----Examples-----
Input
14
.L.R...LR..L..

Output
4

Input
5
R....

Output
0

Input
1
.

Output
1



-----Note-----

The first example case is shown on the figure. The four pieces that remain standing vertically are highlighted with orange.

In the second example case, all pieces fall down since the first piece topples all the other pieces.

In the last example case, a single piece has not been pushed in either direction.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: The Meeting Place Cannot Be Changed

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The main road in Bytecity is a straight line from south to north. Conveniently, there are coordinates measured in meters from the southernmost building in north direction.

At some points on the road there are *n* friends, and *i*-th of them is standing at the point *x**i* meters and can move with any speed no greater than *v**i* meters per second in any of the two directions along the road: south or north.

You are to compute the minimum time needed to gather all the *n* friends at some point on the road. Note that the point they meet at doesn't need to have integer coordinate.

Input Specification:
The first line contains single integer *n* (2<=≤<=*n*<=≤<=60<=000) — the number of friends.

The second line contains *n* integers *x*1,<=*x*2,<=...,<=*x**n* (1<=≤<=*x**i*<=≤<=109) — the current coordinates of the friends, in meters.

The third line contains *n* integers *v*1,<=*v*2,<=...,<=*v**n* (1<=≤<=*v**i*<=≤<=109) — the maximum speeds of the friends, in meters per second.

Output Specification:
Print the minimum time (in seconds) needed for all the *n* friends to meet at some point on the road. 

Your answer will be considered correct, if its absolute or relative error isn't greater than 10<=-<=6. Formally, let your answer be *a*, while jury's answer be *b*. Your answer will be considered correct if  holds.

Demo Input:
['3\n7 1 3\n1 2 1\n', '4\n5 10 3 2\n2 3 2 4\n']

Demo Output:
['2.000000000000\n', '1.400000000000\n']

Note:
In the first sample, all friends can gather at the point 5 within 2 seconds. In order to achieve this, the first friend should go south all the time at his maximum speed, while the second and the third friends should go north at their maximum speeds.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Pero is a passionate lover of riddles. The newest type of riddles he has come across requires the solver to check whether the given word is a multigram.

A multigram is a word that consists of concatenating two or more words that are all mutually anagrams. The first of these words is called the root of the multigram. For instance, the word bbabab is a multigram with the root bba because it consists of anagrams bba and bab.

Help Pero solve the riddle by determining whether his word is a multigram and determining its root in case it is. If there are multiple possible roots of the multigram, output the shortest.

Note: Two words are mutually anagrams if one of them can be obtained from the other by changing the letter order.

-----Input-----
The first and only line of input contains a word of length at most $100000$ lowercase English characters.

-----Output-----
If the given word is not a multigram, output -1. Otherwise, output the shortest root of the given word in one line.

-----Examples-----
Sample Input 1:
aaaa
Sample Output 1:
a

Sample Input 2:
ab
Sample Output 2:
-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In Byteland,conversion of numbers between different bases has  always been a herculian task.They always make errors in these conversions.
People in Byteland  always write one of the digits wrong when they convert a number to a new base and write it down.  For example, when they convert
the number 56 into binary (base 2), the correct result should be
"110", but they might instead write down "010" or "111".  They never
accidentally delete or add digits, so they might write down a number with
a leading digit of "0" if this is the digit they get wrong.

You are given Bytelandians' output when converting a number N into base 2 and base 3,
Find out the correct original value of N (in base 10). You can
assume that there is a unique solution for N.

Input
There are 2 lines:
Line 1: The base-2 representation of N, with one digit written
        incorrectly.
Line 2: The base-3 representation of N, with one digit written
        incorrectly.

Output
The correct value of N

Constraints
N ≤ 1 billion

SAMPLE INPUT
1010
212

SAMPLE OUTPUT
14

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a tree T with N vertices. Recall that a tree is a connected graph with N-1 edges.

Determine the minimum number of edges you must add to T to get a new graph G such that G has a Hamiltonian path.

Note: A graph G is said to have a hamiltonian path if and only if there exists a simple path in G that includes every vertex exactly once.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains an integer N — the number of vertices of the tree.
- The next N-1 lines describe the edges. The i-th of these N-1 lines contains two space-separated integers u_{i} and v_{i}, denoting an edge between u_{i} and v_{i}.
    
------ Output Format ------ 

For each test case, output the minimum number of edges to add to the tree T to get a graph with a hamiltonian path.

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

$1 ≤ T ≤ 10^{4}$
$2 ≤ N ≤ 2 \cdot 10^{5}$
$1 ≤ u_{i}, v_{i} ≤ N$
- It is guaranteed that the edges form a tree.
- The sum of $N$ over all test cases won't exceed $2 \cdot 10^{5}$.

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

----- Sample Output 1 ------ 
1
0
----- explanation 1 ------ 
- For the first test case, the tree is as shown below. We only need to add one edge between $(4,5)$ to get a hamiltonian path. The path will be $2 \rightarrow 1 \rightarrow 3 \rightarrow 4 \rightarrow 5$. We could have also added the edge $(2,4)$ instead to get a different hamiltonian path.
- 
- For the second test case, the given tree itself has a hamiltonian path. So there is no need of adding any edges.

----- Sample Input 2 ------ 
1
10
8 2
2 5
5 6
2 3
3 7
7 1
1 9
3 4
7 10

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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The impact factor of a scientific journal is a measure reflecting the average number of citations to articles published in science journals. For this task we are using a simplified formula for calculating the impact factor:\[ \frac{\text {Total count of citations received by articles published in the journal}}{\text {Total number of articles published}} \]

Rounding is always performed upwards. For example the impact factor of the “Journal for ore research and time wasting” that published $38$ articles cited $894$ times is $894 / 38 = 23.53$ rounding up to $24$.

You are the editor of one scientific journal. You know how many articles you are going to publish and the owners are pushing you to reach a specific impact factor. You are wondering how many scientists you will have to bribe to cite your articles to meet the owners demands. Since money is tight you want to bribe the minimal amount of scientists. Each bribed scientist buys you a single citation.

-----Input-----
First and only line of input will contain $2$ integers, $A$ ($1 \leq A \leq 100$), the number of articles you plan to publish and $I$ ($1 \leq I \leq 100$), the impact factor the owners require.

-----Output-----
The first and only line of output should contain one integer, the minimal number of scientists you need to bribe.

-----Examples-----
Sample Input 1:
38 24
Sample Output 1:
875

Sample Input 2:
1 100
Sample Output 2:
100

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The problem uses a simplified TCP/IP address model, please read the statement carefully.

An IP address is a 32-bit integer, represented as a group of four decimal 8-bit integers (without leading zeroes), separated by commas. For example, record 0.255.1.123 shows a correct IP address and records 0.256.1.123 and 0.255.1.01 do not. In the given problem an arbitrary group of four 8-bit integers is a correct IP address.

Our hero Polycarpus still works as a system administrator in some large corporation. He likes beautiful IP addresses. To check if some IP address is beautiful, he should do the following:

  1. write out in a line four 8-bit numbers of the IP address, without the commas; 
  2. check if the resulting string is a palindrome. 



Let us remind you that a palindrome is a string that reads the same from right to left and from left to right.

For example, IP addresses 12.102.20.121 and 0.3.14.130 are beautiful (as strings "1210220121" and "0314130" are palindromes), and IP addresses 1.20.20.1 and 100.4.4.1 are not.

Polycarpus wants to find all beautiful IP addresses that have the given set of digits. Each digit from the set must occur in the IP address at least once. IP address must not contain any other digits. Help him to cope with this difficult task.

Input

The first line contains a single integer n (1 ≤ n ≤ 10) — the number of digits in the set. The second line contains the set of integers a1, a2, ..., an (0 ≤ ai ≤ 9). It is guaranteed that all digits in the set are distinct.

Output

In the first line print a single integer k — the number of beautiful IP addresses that contain the given set of digits. In the following k lines print the IP addresses, one per line in the arbitrary order.

Examples

Input

6
0 1 2 9 8 7


Output

6
78.190.209.187
79.180.208.197
87.190.209.178
89.170.207.198
97.180.208.179
98.170.207.189


Input

1
4


Output

16
4.4.4.4
4.4.4.44
4.4.44.4
4.4.44.44
4.44.4.4
4.44.4.44
4.44.44.4
4.44.44.44
44.4.4.4
44.4.4.44
44.4.44.4
44.4.44.44
44.44.4.4
44.44.4.44
44.44.44.4
44.44.44.44

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Okabe and Future Gadget Laboratory

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Okabe needs to renovate the Future Gadget Laboratory after he tried doing some crazy experiments! The lab is represented as an *n* by *n* square grid of integers. A good lab is defined as a lab in which every number not equal to 1 can be expressed as the sum of a number in the same row and a number in the same column. In other words, for every *x*,<=*y* such that 1<=≤<=*x*,<=*y*<=≤<=*n* and *a**x*,<=*y*<=≠<=1, there should exist two indices *s* and *t* so that *a**x*,<=*y*<==<=*a**x*,<=*s*<=+<=*a**t*,<=*y*, where *a**i*,<=*j* denotes the integer in *i*-th row and *j*-th column.

Help Okabe determine whether a given lab is good!

Input Specification:
The first line of input contains the integer *n* (1<=≤<=*n*<=≤<=50) — the size of the lab. 

The next *n* lines contain *n* space-separated integers denoting a row of the grid. The *j*-th integer in the *i*-th row is *a**i*,<=*j* (1<=≤<=*a**i*,<=*j*<=≤<=105).

Output Specification:
Print "Yes" if the given lab is good and "No" otherwise.

You can output each letter in upper or lower case.

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

Demo Output:
['Yes\n', 'No\n']

Note:
In the first sample test, the 6 in the bottom left corner is valid because it is the sum of the 2 above it and the 4 on the right. The same holds for every number not equal to 1 in this table, so the answer is "Yes".

In the second sample test, the 5 cannot be formed as the sum of an integer in the same row and an integer in the same column. Thus the answer is "No".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have an integer array with unique elements and we want to do the permutations that have an element fixed, in other words, these permutations should have a certain element at the same position than the original.

These permutations will be called: **permutations with one fixed point**.

Let's see an example with an array of four elements and we want the permutations that have a coincidence **only at  index 0**, so these permutations are (the permutations between parenthesis):
``` 
arr = [1, 2, 3, 4]
      (1, 3, 4, 2)
      (1, 4, 2, 3)
Two permutations matching with arr only at index 0
``` 

Let's see the permutations of the same array with only one coincidence at index **1**:
``` 
arr = [1, 2, 3, 4]
      (3, 2, 4, 1)
      (4, 2, 1, 3)
Two permutations matching with arr only at index 1
```
Once again, let's see the permutations of the same array with only one coincidence at index **2**:
``` 
arr = [1, 2, 3, 4]
      (2, 4, 3, 1)
      (4, 1, 3, 2)
Two permutations matching with arr only at index 2
```
Finally, let's see the permutations of the same array with only one coincidence at index **3**:
``` 
arr = [1, 2, 3, 4]
      (2, 3, 1, 4)
      (3, 1, 2, 4)
Two permutations matching with arr only at index 3
```
For this array given above (arr) :

- We conclude that we have 8 permutations with one fixed point (two at each index of arr).

- We may do the same development for our array, `arr`, with two fixed points and we will get `6` permutations.

- There are no permutations with coincidences only at three indexes.

- It's good to know that the amount of permutations with no coincidences at all are `9`. See the kata Shuffle It Up!!

In general:

- When the amount of fixed points is equal to the array length, there is only one permutation, the original array.

- When the amount of fixed points surpasses the length of the array, obvously, there are no permutations at all.

Create a function that receives the length of the array and the number of fixed points and may output the total amount of permutations for these constraints.

Features of the random tests:
```
length of the array = l
number of fixed points = k
10 ≤ k ≤ l ≤ 9000
```
See the example tests!
Enjoy it!!

Ruby versin will be released soon.

#Note: This kata was published previously but in a version not well optimized.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have a string S of length N. Initially, all characters in S are `1`s.

You will perform queries Q times. In the i-th query, you are given two integers L_i, R_i and a character D_i (which is a digit). Then, you must replace all characters from the L_i-th to the R_i-th (inclusive) with D_i.

After each query, read the string S as a decimal integer, and print its value modulo 998,244,353.

Constraints

* 1 \leq N, Q \leq 200,000
* 1 \leq L_i \leq R_i \leq N
* 1 \leq D_i \leq 9
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N Q
L_1 R_1 D_1
:
L_Q R_Q D_Q


Output

Print Q lines. In the i-th line print the value of S after the i-th query, modulo 998,244,353.

Examples

Input

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


Output

11222211
77772211
77333333
72333333
72311333


Input

200000 1
123 456 7


Output

641437905

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Max wants to buy a new skateboard. He has calculated the amount of money that is needed to buy a new skateboard. He left a calculator on the floor and went to ask some money from his parents. Meanwhile his little brother Yusuf came and started to press the keys randomly. Unfortunately Max has forgotten the number which he had calculated. The only thing he knows is that the number is divisible by 4.

You are given a string s consisting of digits (the number on the display of the calculator after Yusuf randomly pressed the keys). Your task is to find the number of substrings which are divisible by 4. A substring can start with a zero.

A substring of a string is a nonempty sequence of consecutive characters.

For example if string s is 124 then we have four substrings that are divisible by 4: 12, 4, 24 and 124. For the string 04 the answer is three: 0, 4, 04.

As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use gets/scanf/printf instead of getline/cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.


-----Input-----

The only line contains string s (1 ≤ |s| ≤ 3·10^5). The string s contains only digits from 0 to 9.


-----Output-----

Print integer a — the number of substrings of the string s that are divisible by 4.

Note that the answer can be huge, so you should use 64-bit integer type to store it. In C++ you can use the long long integer type and in Java you can use long integer type.


-----Examples-----
Input
124

Output
4

Input
04

Output
3

Input
5810438174

Output
9

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