vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You are given an integer N. You have to count the number of distinct tuples (A, B, C, D) with 1 ≤ A, B, C, D ≤ N such that A \cdot B = C \cdot D. 

Two tuples, say (A, B, C, D) and (E, F, G, H) are considered to be different if at least one of the following conditions hold true: 
A \neq E 
B \neq F
C \neq G
D \neq H.

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

- First line will contain T, number of testcases. Then the testcases follow.
- Each testcase contains a single integer on a new line - N, as described in the problem statement

------ Output Format ------ 

For each testcase, output the answer on a new line - the number of tuples as described in the problem statement.

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

$1 ≤ T ≤ 10$
$1 ≤ N ≤ 10^{6}$

----- Sample Input 1 ------ 
3
3
50
35
----- Sample Output 1 ------ 
15
10950
4831
----- explanation 1 ------ 
Test case $1$:
Following tuples satisfy the given condition:
- (1, 1, 1, 1)
- (1, 2, 2, 1)
- (1, 3, 3, 1)
- (2, 1, 1, 2)
- (2, 2, 2, 2)
- (2, 3, 3, 2)
- (3, 1, 1, 3)
- (3, 2, 2, 3)
- (3, 3, 3, 3)
- (1, 2, 1, 2)
- (2, 1, 2, 1)
- (1, 3, 1, 3)
- (3, 1, 3, 1)
- (2, 3, 2, 3)
- (3, 2, 3, 2)

$A \cdot B = C \cdot D$ holds true for all these tuples.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Recently Vasya learned that, given two points with different $x$ coordinates, you can draw through them exactly one parabola with equation of type $y = x^2 + bx + c$, where $b$ and $c$ are reals. Let's call such a parabola an $U$-shaped one.

Vasya drew several distinct points with integer coordinates on a plane and then drew an $U$-shaped parabola through each pair of the points that have different $x$ coordinates. The picture became somewhat messy, but Vasya still wants to count how many of the parabolas drawn don't have any drawn point inside their internal area. Help Vasya.

The internal area of an $U$-shaped parabola is the part of the plane that lies strictly above the parabola when the $y$ axis is directed upwards.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 100\,000$) — the number of points.

The next $n$ lines describe the points, the $i$-th of them contains two integers $x_i$ and $y_i$ — the coordinates of the $i$-th point. It is guaranteed that all points are distinct and that the coordinates do not exceed $10^6$ by absolute value.


-----Output-----

In the only line print a single integer — the number of $U$-shaped parabolas that pass through at least two of the given points and do not contain any of the given points inside their internal area (excluding the parabola itself).


-----Examples-----
Input
3
-1 0
0 2
1 0

Output
2

Input
5
1 0
1 -1
0 -1
-1 0
-1 -1

Output
1



-----Note-----

On the pictures below all $U$-shaped parabolas that pass through at least two given points are drawn for each of the examples. The $U$-shaped parabolas that do not have any given point inside their internal area are drawn in red.  [Image] The first example. 

 [Image] The second example.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string of a constant length, print a triangle out of it. The triangle should start with the given string and keeps shrinking downwards by removing one character from the begining of the string. The spaces on the left side of the triangle should be replaced with dot character.
 
Example 1: 
Input:
S = Geeks
Output:
Geeks
.eeks
..eks
...ks
....s
Example 2: 
Input:
S = @io30 
Output:
 @io30
.io30
..o30
...30
....0 
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function triDownwards() which takes a String S and returns a string formed by joining all the lines together. For the Input "GEEKS" you should return the String "GEEKS.EEKS..EKS...KS....S".
 
Expected Time Complexity: O(|S|^{2})
Expected Auxiliary Space: O(|S|)
 
Constraints:
1 <= |S| <=100

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider the following $4 \times 4$ pattern:
1  2  4  7
3  5  8 11
6  9 12 14
10 13 15 16

You are given an integer $N$. Print the $N \times N$ pattern of the same kind (containing integers $1$ through $N^2$).

-----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 and only line of each test case contains a single integer $N$.

-----Output-----
For each test case, print $N$ lines; each of them should contain $N$ space-separated integers.

-----Constraints-----
- $1 \le T \le 10$
- $1 \le N \le 100$

-----Subtasks-----
Subtask #1 (100 points): Original constraints

-----Example Input-----
1
4

-----Example Output-----
1 2 4 7
3 5 8 11
6 9 12 14
10 13 15 16

-----Explanation-----

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Indian National Olympiad in Informatics 2013
N people live in Sequence Land. Instead of a name, each person is identified by a sequence of integers, called his or her id. Each id is a sequence with no duplicate elements. Two people are said to be each other’s relatives if their ids have at least K elements in common. The extended family of a resident of Sequence Land includes herself or himself, all relatives, relatives of relatives, relatives of relatives of relatives, and so on without any limit.
Given the ids of all residents of Sequence Land, including its President, and the number K, find the number of people in the extended family of the President of Sequence Land.
For example, suppose N = 4 and K = 2. Suppose the President has id (4, 6, 7, 8) and the other three residents have ids (8, 3, 0, 4), (0, 10), and (1, 2, 3, 0, 5, 8). Here, the President is directly related to (8, 3, 0, 4), who in turn is directly related to (1, 2, 3, 0, 5, 8). Thus, the President’s extended family consists of everyone other than (0, 10) and so has size 3.

-----Input format-----
• Line 1: Two space-separated integers, N followed by K.
• Lines 2 to N + 1: Each line describes an id of one of the residents of Sequence Land, beginning with the President on line 2. Each line consists of an integer p, followed by p distinct integers, the id.

-----Output format-----
The output consists of a single integer, the number of people in the extended family of the President.

-----Test Data-----
The testdata is grouped into two subtasks. In both subtasks, 1 ≤ N ≤ 300 and 1 ≤ K ≤ 300. Each number in each id is between 0 and 109 inclusive.
• Subtask 1 [30 points]: The number of elements in each id is between 1 and 10 inclusive.
• Subtask 2 [70 points]: The number of elements in each id is between 1 and 300 inclusive.

-----Example-----
Here is the sample input and output corresponding to the example above.

-----Sample input -----
4 2
4 4 6 7 8
4 8 3 0 4
2 0 10
6 1 2 3 0 5 8

-----Sample output-----
3

Note: Your program should not print anything other than what is specified in the output format. Please remove all diagnostic print statements before making your final submission. A program with extraneous output will be treated as incorrect!

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
There are five people playing a game called "Generosity". Each person gives some non-zero number of coins *b* as an initial bet. After all players make their bets of *b* coins, the following operation is repeated for several times: a coin is passed from one player to some other player.

Your task is to write a program that can, given the number of coins each player has at the end of the game, determine the size *b* of the initial bet or find out that such outcome of the game cannot be obtained for any positive number of coins *b* in the initial bet.

Input Specification:
The input consists of a single line containing five integers *c*1,<=*c*2,<=*c*3,<=*c*4 and *c*5 — the number of coins that the first, second, third, fourth and fifth players respectively have at the end of the game (0<=≤<=*c*1,<=*c*2,<=*c*3,<=*c*4,<=*c*5<=≤<=100).

Output Specification:
Print the only line containing a single positive integer *b* — the number of coins in the initial bet of each player. If there is no such value of *b*, then print the only value "-1" (quotes for clarity).

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

Demo Output:
['3\n', '-1\n']

Note:
In the first sample the following sequence of operations is possible:
 1.  One coin is passed from the fourth player to the second player; 1.  One coin is passed from the fourth player to the fifth player; 1.  One coin is passed from the first player to the third player; 1.  One coin is passed from the fourth player to the second player.

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

Time Limit: 1 seconds

Memory Limit: 256 megabytes

Problem Description:
It is nighttime and Joe the Elusive got into the country's main bank's safe. The safe has *n* cells positioned in a row, each of them contains some amount of diamonds. Let's make the problem more comfortable to work with and mark the cells with positive numbers from 1 to *n* from the left to the right.

Unfortunately, Joe didn't switch the last security system off. On the plus side, he knows the way it works.

Every minute the security system calculates the total amount of diamonds for each two adjacent cells (for the cells between whose numbers difference equals 1). As a result of this check we get an *n*<=-<=1 sums. If at least one of the sums differs from the corresponding sum received during the previous check, then the security system is triggered.

Joe can move the diamonds from one cell to another between the security system's checks. He manages to move them no more than *m* times between two checks. One of the three following operations is regarded as moving a diamond: moving a diamond from any cell to any other one, moving a diamond from any cell to Joe's pocket, moving a diamond from Joe's pocket to any cell. Initially Joe's pocket is empty, and it can carry an unlimited amount of diamonds. It is considered that before all Joe's actions the system performs at least one check.

In the morning the bank employees will come, which is why Joe has to leave the bank before that moment. Joe has only *k* minutes left before morning, and on each of these *k* minutes he can perform no more than *m* operations. All that remains in Joe's pocket, is considered his loot.

Calculate the largest amount of diamonds Joe can carry with him. Don't forget that the security system shouldn't be triggered (even after Joe leaves the bank) and Joe should leave before morning.

Input Specification:
The first line contains integers *n*, *m* and *k* (1<=≤<=*n*<=≤<=104, 1<=≤<=*m*,<=*k*<=≤<=109). The next line contains *n* numbers. The *i*-th number is equal to the amount of diamonds in the *i*-th cell — it is an integer from 0 to 105.

Output Specification:
Print a single number — the maximum number of diamonds Joe can steal.

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

Demo Output:
['0', '2']

Note:
In the second sample Joe can act like this:

The diamonds' initial positions are 4 1 3.

During the first period of time Joe moves a diamond from the 1-th cell to the 2-th one and a diamond from the 3-th cell to his pocket.

By the end of the first period the diamonds' positions are 3 2 2. The check finds no difference and the security system doesn't go off.

During the second period Joe moves a diamond from the 3-rd cell to the 2-nd one and puts a diamond from the 1-st cell to his pocket.

By the end of the second period the diamonds' positions are 2 3 1. The check finds no difference again and the security system doesn't go off.

Now Joe leaves with 2 diamonds in his pocket.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N cubes stacked vertically on a desk.
You are given a string S of length N. The color of the i-th cube from the bottom is red if the i-th character in S is 0, and blue if that character is 1.
You can perform the following operation any number of times: choose a red cube and a blue cube that are adjacent, and remove them. Here, the cubes that were stacked on the removed cubes will fall down onto the object below them.
At most how many cubes can be removed?

-----Constraints-----
 - 1 \leq N \leq 10^5
 - |S| = N
 - Each character in S is 0 or 1.

-----Input-----
Input is given from Standard Input in the following format:
S

-----Output-----
Print the maximum number of cubes that can be removed.

-----Sample Input-----
0011

-----Sample Output-----
4

All four cubes can be removed, by performing the operation as follows:
 - Remove the second and third cubes from the bottom. Then, the fourth cube drops onto the first cube.
 - Remove the first and second cubes from the bottom.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Task
 Let's call `product(x)` the product of x's digits. Given an array of integers a, calculate `product(x)` for each x in a, and return the number of distinct results you get.

# Example

 For `a = [2, 8, 121, 42, 222, 23]`, the output should be `3`.

 Here are the products of the array's elements:
```
2: product(2) = 2;
8: product(8) = 8;
121: product(121) = 1 * 2 * 1 = 2;
42: product(42) = 4 * 2 = 8;
222: product(222) = 2 * 2 * 2 = 8;
23: product(23) = 2 * 3 = 6.```
As you can see, there are only `3` different products: `2, 6 and 8.`

# Input/Output


 - `[input]` integer array `a`

    Constraints:

    `1 ≤ a.length ≤ 10000,`

    `1 ≤ a[i] ≤ 1000000000.`


 - `[output]` an integer

    The number of different digit products in `a`.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Valery is a PE teacher at a school in Berland. Soon the students are going to take a test in long jumps, and Valery has lost his favorite ruler! 

However, there is no reason for disappointment, as Valery has found another ruler, its length is l centimeters. The ruler already has n marks, with which he can make measurements. We assume that the marks are numbered from 1 to n in the order they appear from the beginning of the ruler to its end. The first point coincides with the beginning of the ruler and represents the origin. The last mark coincides with the end of the ruler, at distance l from the origin. This ruler can be repesented by an increasing sequence a_1, a_2, ..., a_{n}, where a_{i} denotes the distance of the i-th mark from the origin (a_1 = 0, a_{n} = l).

Valery believes that with a ruler he can measure the distance of d centimeters, if there is a pair of integers i and j (1 ≤ i ≤ j ≤ n), such that the distance between the i-th and the j-th mark is exactly equal to d (in other words, a_{j} - a_{i} = d). 

Under the rules, the girls should be able to jump at least x centimeters, and the boys should be able to jump at least y (x < y) centimeters. To test the children's abilities, Valery needs a ruler to measure each of the distances x and y. 

Your task is to determine what is the minimum number of additional marks you need to add on the ruler so that they can be used to measure the distances x and y. Valery can add the marks at any integer non-negative distance from the origin not exceeding the length of the ruler.


-----Input-----

The first line contains four positive space-separated integers n, l, x, y (2 ≤ n ≤ 10^5, 2 ≤ l ≤ 10^9, 1 ≤ x < y ≤ l) — the number of marks, the length of the ruler and the jump norms for girls and boys, correspondingly.

The second line contains a sequence of n integers a_1, a_2, ..., a_{n} (0 = a_1 < a_2 < ... < a_{n} = l), where a_{i} shows the distance from the i-th mark to the origin.


-----Output-----

In the first line print a single non-negative integer v — the minimum number of marks that you need to add on the ruler.

In the second line print v space-separated integers p_1, p_2, ..., p_{v} (0 ≤ p_{i} ≤ l). Number p_{i} means that the i-th mark should be at the distance of p_{i} centimeters from the origin. Print the marks in any order. If there are multiple solutions, print any of them.


-----Examples-----
Input
3 250 185 230
0 185 250

Output
1
230

Input
4 250 185 230
0 20 185 250

Output
0

Input
2 300 185 230
0 300

Output
2
185 230



-----Note-----

In the first sample it is impossible to initially measure the distance of 230 centimeters. For that it is enough to add a 20 centimeter mark or a 230 centimeter mark.

In the second sample you already can use the ruler to measure the distances of 185 and 230 centimeters, so you don't have to add new marks.

In the third sample the ruler only contains the initial and the final marks. We will need to add two marks to be able to test the children's skills.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# How much is the fish! (- Scooter )
The ocean is full of colorful fishes. We as programmers want to know the hexadecimal value of these fishes.

## Task
Take all hexadecimal valid characters (a,b,c,d,e,f) of the given name and XOR them. Return the result as an integer.

## Input
The input is always a string, which can contain spaces, upper and lower case letters but no digits. 

## Example

`fisHex("redlionfish") -> e,d,f -> XOR -> 12`

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given matrix with n rows and n columns filled with zeroes. You should put k ones in it in such a way that the resulting matrix is symmetrical with respect to the main diagonal (the diagonal that goes from the top left to the bottom right corner) and is lexicographically maximal.

One matrix is lexicographically greater than the other if the first different number in the first different row from the top in the first matrix is greater than the corresponding number in the second one.

If there exists no such matrix then output -1.

Input

The first line consists of two numbers n and k (1 ≤ n ≤ 100, 0 ≤ k ≤ 106).

Output

If the answer exists then output resulting matrix. Otherwise output -1.

Examples

Input

2 1


Output

1 0 
0 0 


Input

3 2


Output

1 0 0 
0 1 0 
0 0 0 


Input

2 5


Output

-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It is finally Bobby’s birthday, and all of his Acquaintances, Buddies and Colleagues have gathered for a board game night. They are going to play a board game which is played in up to three big teams. Bobby decided to split his guests into groups based on how well he knows them: the Acquaintances on team $A$, the Buddies on team $B$, and the Colleagues on team $C$.

While Bobby was busy explaining the rules to everyone, all his guests already took seats around his large, circular living room table. However, for the game it is crucial that all people sitting on a team are sitting next to each other. Otherwise, members of other teams could easily eavesdrop on their planning, ruining the game. So some people may need to change seats to avoid this from happening.

Bobby wants to start playing the game as soon as possible, so he wants people to switch seats as efficiently as possible. Given the current arrangement around the circular table, can you figure out the minimal number of people that must switch seats so that the teams are lined up correctly?

-----Input-----
 - The first line of the input contains the integer $n$, where $1 \leq n \leq 10^5$ is the number of players (as well as seats).
 - The second line contains a string of length $n$, consisting only of the characters in ABC. This indicates the teams of the people sitting around the table in order.

-----Output-----
Print a single integer: the minimal number of people you have to ask to move seats to make sure the teams sit together.

-----Examples-----
Sample Input 1:
5
ABABC
Sample Output 1:
2

Sample Input 2:
12
ABCABCABCABC
Sample Output 2:
6

Sample Input 3:
4
ACBA
Sample Output 3:
0

Sample Input 4:
6
BABABA
Sample Output 4:
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp wants to train before another programming competition. During the first day of his training he should solve exactly $1$ problem, during the second day — exactly $2$ problems, during the third day — exactly $3$ problems, and so on. During the $k$-th day he should solve $k$ problems.

Polycarp has a list of $n$ contests, the $i$-th contest consists of $a_i$ problems. During each day Polycarp has to choose exactly one of the contests he didn't solve yet and solve it. He solves exactly $k$ problems from this contest. Other problems are discarded from it. If there are no contests consisting of at least $k$ problems that Polycarp didn't solve yet during the $k$-th day, then Polycarp stops his training.

How many days Polycarp can train if he chooses the contests optimally?


-----Input-----

The first line of the input contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of contests.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 2 \cdot 10^5$) — the number of problems in the $i$-th contest.


-----Output-----

Print one integer — the maximum number of days Polycarp can train if he chooses the contests optimally.


-----Examples-----
Input
4
3 1 4 1

Output
3

Input
3
1 1 1

Output
1

Input
5
1 1 1 2 2

Output
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Micro's midsem exams are finally over. When they were going on, instead of studying he would spend time making list of things that he wanted to do after the exams. But, now when they are over, he has lost the list. He was feeling very low, so his roommate Naik gave him a game to kill time. 

He gave him N blocks. Each block is having a number on top of it. Now Micro has to arrange them in a row, such that the Fun Number is maximized.

Fun Number is the number that he will get by concatenating the numbers on each block, from left to right. For, example if there are 3 blocks with numbers 12, 3, 2 on top arranged as 2, 3, 12, then the Fun Number is 2312 (see sample explanation for more clarity). Micro being a programmer thought of finding the maximum Fun Number by writing a program for it. Micro is an excellent programmer but he is not so good with algorithms, so he asks for your help in solving this problem.

Input:
The first line consist of an integer N, the number of blocks.  The second line consist of N integers separated by space, the number written on top of each block.

Output:
Output the maximum Fun Number that Micro can get.

Constraints:
1 ≤ N ≤ 10^5
1 ≤ Number on each block ≤ 10^9

SAMPLE INPUT
3
12 2 3

SAMPLE OUTPUT
3212Explanation

All possible arrangements are:
12 2 3, Fun Number = 1223
12 3 2, Fun Number = 1232
2 3 12, Fun Number = 2312 
2 12 3, Fun Number = 2123
3 12 2, Fun Number = 3122
3 2 12, Fun Number = 3212
So, the maximum Fun Number that Micro can get is 3212

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