meetforever/GRPO_CL huggingface dataset:
user: Gildong has bought a famous painting software cfpaint. The working screen of cfpaint is square-shaped consisting of $n$ rows and $n$ columns of square cells. The rows are numbered from $1$ to $n$, from top to bottom, and the columns are numbered from $1$ to $n$, from left to right. The position of a cell at row $r$ and column $c$ is represented as $(r, c)$. There are only two colors for the cells in cfpaint — black and white.

There is a tool named eraser in cfpaint. The eraser has an integer size $k$ ($1 \le k \le n$). To use the eraser, Gildong needs to click on a cell $(i, j)$ where $1 \le i, j \le n - k + 1$. When a cell $(i, j)$ is clicked, all of the cells $(i', j')$ where $i \le i' \le i + k - 1$ and $j \le j' \le j + k - 1$ become white. In other words, a square with side equal to $k$ cells and top left corner at $(i, j)$ is colored white.

A white line is a row or a column without any black cells.

Gildong has worked with cfpaint for some time, so some of the cells (possibly zero or all) are currently black. He wants to know the maximum number of white lines after using the eraser exactly once. Help Gildong find the answer to his question.


-----Input-----

The first line contains two integers $n$ and $k$ ($1 \le k \le n \le 2000$) — the number of rows and columns, and the size of the eraser.

The next $n$ lines contain $n$ characters each without spaces. The $j$-th character in the $i$-th line represents the cell at $(i,j)$. Each character is given as either 'B' representing a black cell, or 'W' representing a white cell.


-----Output-----

Print one integer: the maximum number of white lines after using the eraser exactly once.


-----Examples-----
Input
4 2
BWWW
WBBW
WBBW
WWWB

Output
4

Input
3 1
BWB
WWB
BWB

Output
2

Input
5 3
BWBBB
BWBBB
BBBBB
BBBBB
WBBBW

Output
2

Input
2 2
BW
WB

Output
4

Input
2 1
WW
WW

Output
4



-----Note-----

In the first example, Gildong can click the cell $(2, 2)$, then the working screen becomes: BWWW

WWWW

WWWW

WWWB



Then there are four white lines — the $2$-nd and $3$-rd row, and the $2$-nd and $3$-rd column.

In the second example, clicking the cell $(2, 3)$ makes the $2$-nd row a white line.

In the third example, both the $2$-nd column and $5$-th row become white lines by clicking the cell $(3, 2)$.
user: Mishka has got n empty boxes. For every i (1 ≤ i ≤ n), i-th box is a cube with side length a_{i}.

Mishka can put a box i into another box j if the following conditions are met:

  i-th box is not put into another box;  j-th box doesn't contain any other boxes;  box i is smaller than box j (a_{i} < a_{j}). 

Mishka can put boxes into each other an arbitrary number of times. He wants to minimize the number of visible boxes. A box is called visible iff it is not put into some another box.

Help Mishka to determine the minimum possible number of visible boxes!


-----Input-----

The first line contains one integer n (1 ≤ n ≤ 5000) — the number of boxes Mishka has got.

The second line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9), where a_{i} is the side length of i-th box.


-----Output-----

Print the minimum possible number of visible boxes.


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

Output
1

Input
4
4 2 4 3

Output
2



-----Note-----

In the first example it is possible to put box 1 into box 2, and 2 into 3.

In the second example Mishka can put box 2 into box 3, and box 4 into box 1.
user: Arthur has bought a beautiful big table into his new flat. When he came home, Arthur noticed that the new table is unstable.

In total the table Arthur bought has n legs, the length of the i-th leg is l_{i}.

Arthur decided to make the table stable and remove some legs. For each of them Arthur determined number d_{i} — the amount of energy that he spends to remove the i-th leg.

A table with k legs is assumed to be stable if there are more than half legs of the maximum length. For example, to make a table with 5 legs stable, you need to make sure it has at least three (out of these five) legs of the maximum length. Also, a table with one leg is always stable and a table with two legs is stable if and only if they have the same lengths.

Your task is to help Arthur and count the minimum number of energy units Arthur should spend on making the table stable.


-----Input-----

The first line of the input contains integer n (1 ≤ n ≤ 10^5) — the initial number of legs in the table Arthur bought.

The second line of the input contains a sequence of n integers l_{i} (1 ≤ l_{i} ≤ 10^5), where l_{i} is equal to the length of the i-th leg of the table.

The third line of the input contains a sequence of n integers d_{i} (1 ≤ d_{i} ≤ 200), where d_{i} is the number of energy units that Arthur spends on removing the i-th leg off the table.


-----Output-----

Print a single integer — the minimum number of energy units that Arthur needs to spend in order to make the table stable.


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

Output
2

Input
3
2 4 4
1 1 1

Output
0

Input
6
2 2 1 1 3 3
4 3 5 5 2 1

Output
8
user: The R2 company has n employees working for it. The work involves constant exchange of ideas, sharing the stories of success and upcoming challenging. For that, R2 uses a famous instant messaging program Spyke.

R2 has m Spyke chats just to discuss all sorts of issues. In each chat, some group of employees exchanges messages daily. An employee can simultaneously talk in multiple chats. If some employee is in the k-th chat, he can write messages to this chat and receive notifications about messages from this chat. If an employee writes a message in the chat, all other participants of the chat receive a message notification.

The R2 company is conducting an audit. Now the specialists study effective communication between the employees. For this purpose, they have a chat log and the description of chat structure. You, as one of audit specialists, are commissioned to write a program that will use this data to determine the total number of message notifications received by each employee.


-----Input-----

The first line contains three space-separated integers n, m and k (2 ≤ n ≤ 2·10^4; 1 ≤ m ≤ 10; 1 ≤ k ≤ 2·10^5) — the number of the employees, the number of chats and the number of events in the log, correspondingly. 

Next n lines contain matrix a of size n × m, consisting of numbers zero and one. The element of this matrix, recorded in the j-th column of the i-th line, (let's denote it as a_{ij}) equals 1, if the i-th employee is the participant of the j-th chat, otherwise the element equals 0. Assume that the employees are numbered from 1 to n and the chats are numbered from 1 to m.

Next k lines contain the description of the log events. The i-th line contains two space-separated integers x_{i} and y_{i} (1 ≤ x_{i} ≤ n; 1 ≤ y_{i} ≤ m) which mean that the employee number x_{i} sent one message to chat number y_{i}. It is guaranteed that employee number x_{i} is a participant of chat y_{i}. It is guaranteed that each chat contains at least two employees.


-----Output-----

Print in the single line n space-separated integers, where the i-th integer shows the number of message notifications the i-th employee receives.


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

Output
3 3 1 
Input
4 3 4
0 1 1
1 0 1
1 1 1
0 0 0
1 2
2 1
3 1
1 3

Output
0 2 3 0
user: You have a description of a lever as string s. We'll represent the string length as record |s|, then the lever looks as a horizontal bar with weights of length |s| - 1 with exactly one pivot. We will assume that the bar is a segment on the Ox axis between points 0 and |s| - 1.

The decoding of the lever description is given below.

  If the i-th character of the string equals "^", that means that at coordinate i there is the pivot under the bar.  If the i-th character of the string equals "=", that means that at coordinate i there is nothing lying on the bar.  If the i-th character of the string equals digit c (1-9), that means that at coordinate i there is a weight of mass c on the bar. 

Your task is, given the lever description, print if it will be in balance or not. Assume that the bar doesn't weight anything. Assume that the bar initially is in balance then all weights are simultaneously put on it. After that the bar either tilts to the left, or tilts to the right, or is in balance.


-----Input-----

The first line contains the lever description as a non-empty string s (3 ≤ |s| ≤ 10^6), consisting of digits (1-9) and characters "^" and "=". It is guaranteed that the line contains exactly one character "^". It is guaranteed that the pivot of the lever isn't located in any end of the lever bar.

To solve the problem you may need 64-bit integer numbers. Please, do not forget to use them in your programs.


-----Output-----

Print "left" if the given lever tilts to the left, "right" if it tilts to the right and "balance", if it is in balance.


-----Examples-----
Input
=^==

Output
balance

Input
9===^==1

Output
left

Input
2==^7==

Output
right

Input
41^52==

Output
balance



-----Note-----

As you solve the problem, you may find the following link useful to better understand how a lever functions: http://en.wikipedia.org/wiki/Lever.

The pictures to the examples:

 [Image] 

 [Image] 

 [Image] 

 $\Delta \Delta \Delta \Delta$
user: Vasiliy likes to rest after a hard work, so you may often meet him in some bar nearby. As all programmers do, he loves the famous drink "Beecola", which can be bought in n different shops in the city. It's known that the price of one bottle in the shop i is equal to x_{i} coins.

Vasiliy plans to buy his favorite drink for q consecutive days. He knows, that on the i-th day he will be able to spent m_{i} coins. Now, for each of the days he want to know in how many different shops he can buy a bottle of "Beecola".


-----Input-----

The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of shops in the city that sell Vasiliy's favourite drink.

The second line contains n integers x_{i} (1 ≤ x_{i} ≤ 100 000) — prices of the bottles of the drink in the i-th shop.

The third line contains a single integer q (1 ≤ q ≤ 100 000) — the number of days Vasiliy plans to buy the drink.

Then follow q lines each containing one integer m_{i} (1 ≤ m_{i} ≤ 10^9) — the number of coins Vasiliy can spent on the i-th day.


-----Output-----

Print q integers. The i-th of them should be equal to the number of shops where Vasiliy will be able to buy a bottle of the drink on the i-th day.


-----Example-----
Input
5
3 10 8 6 11
4
1
10
3
11

Output
0
4
1
5



-----Note-----

On the first day, Vasiliy won't be able to buy a drink in any of the shops.

On the second day, Vasiliy can buy a drink in the shops 1, 2, 3 and 4.

On the third day, Vasiliy can buy a drink only in the shop number 1.

Finally, on the last day Vasiliy can buy a drink in any shop.
user: Because of budget cuts one IT company established new non-financial reward system instead of bonuses.

Two kinds of actions are rewarded: fixing critical bugs and suggesting new interesting features. A man who fixed a critical bug gets "I fixed a critical bug" pennant on his table. A man who suggested a new interesting feature gets "I suggested a new feature" pennant on his table.

Because of the limited budget of the new reward system only 5 "I fixed a critical bug" pennants and 3 "I suggested a new feature" pennants were bought.

In order to use these pennants for a long time they were made challenge ones. When a man fixes a new critical bug one of the earlier awarded "I fixed a critical bug" pennants is passed on to his table. When a man suggests a new interesting feature one of the earlier awarded "I suggested a new feature" pennants is passed on to his table.

One man can have several pennants of one type and of course he can have pennants of both types on his table. There are n tables in the IT company. Find the number of ways to place the pennants on these tables given that each pennant is situated on one of the tables and each table is big enough to contain any number of pennants.


-----Input-----

The only line of the input contains one integer n (1 ≤ n ≤ 500) — the number of tables in the IT company.


-----Output-----

Output one integer — the amount of ways to place the pennants on n tables.


-----Examples-----
Input
2

Output
24
user: One day Vasya came up to the blackboard and wrote out n distinct integers from 1 to n in some order in a circle. Then he drew arcs to join the pairs of integers (a, b) (a ≠ b), that are either each other's immediate neighbors in the circle, or there is number c, such that a and с are immediate neighbors, and b and c are immediate neighbors. As you can easily deduce, in the end Vasya drew 2·n arcs.

For example, if the numbers are written in the circle in the order 1, 2, 3, 4, 5 (in the clockwise direction), then the arcs will join pairs of integers (1, 2), (2, 3), (3, 4), (4, 5), (5, 1), (1, 3), (2, 4), (3, 5), (4, 1) and (5, 2).

Much time has passed ever since, the numbers we wiped off the blackboard long ago, but recently Vasya has found a piece of paper with 2·n written pairs of integers that were joined with the arcs on the board. Vasya asks you to find the order of numbers in the circle by these pairs.


-----Input-----

The first line of the input contains a single integer n (5 ≤ n ≤ 10^5) that shows, how many numbers were written on the board. Next 2·n lines contain pairs of integers a_{i}, b_{i} (1 ≤ a_{i}, b_{i} ≤ n, a_{i} ≠ b_{i}) — the numbers that were connected by the arcs.

It is guaranteed that no pair of integers, connected by a arc, occurs in the input more than once. The pairs of numbers and the numbers in the pairs are given in the arbitrary order.


-----Output-----

If Vasya made a mistake somewhere and there isn't any way to place numbers from 1 to n on the circle according to the statement, then print a single number "-1" (without the quotes). Otherwise, print any suitable sequence of n distinct integers from 1 to n. 

If there are multiple solutions, you are allowed to print any of them. Specifically, it doesn't matter which number you write first to describe the sequence of the order. It also doesn't matter whether you write out the numbers in the clockwise or counter-clockwise direction.


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

Output
1 2 3 4 5 
Input
6
5 6
4 3
5 3
2 4
6 1
3 1
6 2
2 5
1 4
3 6
1 2
4 5

Output
1 2 4 5 3 6
user: Kris works in a large company "Blake Technologies". As a best engineer of the company he was assigned a task to develop a printer that will be able to print horizontal and vertical strips. First prototype is already built and Kris wants to tests it. He wants you to implement the program that checks the result of the printing.

Printer works with a rectangular sheet of paper of size n × m. Consider the list as a table consisting of n rows and m columns. Rows are numbered from top to bottom with integers from 1 to n, while columns are numbered from left to right with integers from 1 to m. Initially, all cells are painted in color 0.

Your program has to support two operations:   Paint all cells in row r_{i} in color a_{i};  Paint all cells in column c_{i} in color a_{i}. 

If during some operation i there is a cell that have already been painted, the color of this cell also changes to a_{i}.

Your program has to print the resulting table after k operation.


-----Input-----

The first line of the input contains three integers n, m and k (1  ≤  n,  m  ≤ 5000, n·m ≤ 100 000, 1 ≤ k ≤ 100 000) — the dimensions of the sheet and the number of operations, respectively.

Each of the next k lines contains the description of exactly one query:   1 r_{i} a_{i} (1 ≤ r_{i} ≤ n, 1 ≤ a_{i} ≤ 10^9), means that row r_{i} is painted in color a_{i};  2 c_{i} a_{i} (1 ≤ c_{i} ≤ m, 1 ≤ a_{i} ≤ 10^9), means that column c_{i} is painted in color a_{i}. 


-----Output-----

Print n lines containing m integers each — the resulting table after all operations are applied.


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

Output
3 1 3 
2 2 2 
0 1 0 

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

Output
1 1 1 
1 0 1 
1 1 1 
1 0 1 
1 1 1 



-----Note-----

The figure below shows all three operations for the first sample step by step. The cells that were painted on the corresponding step are marked gray.  [Image]
user: Gardener Alexey teaches competitive programming to high school students. To congratulate Alexey on the Teacher's Day, the students have gifted him a collection of wooden sticks, where every stick has an integer length. Now Alexey wants to grow a tree from them.

The tree looks like a polyline on the plane, consisting of all sticks. The polyline starts at the point $(0, 0)$. While constructing the polyline, Alexey will attach sticks to it one by one in arbitrary order. Each stick must be either vertical or horizontal (that is, parallel to $OX$ or $OY$ axis). It is not allowed for two consecutive sticks to be aligned simultaneously horizontally or simultaneously vertically. See the images below for clarification.

Alexey wants to make a polyline in such a way that its end is as far as possible from $(0, 0)$. Please help him to grow the tree this way.

Note that the polyline defining the form of the tree may have self-intersections and self-touches, but it can be proved that the optimal answer does not contain any self-intersections or self-touches.


-----Input-----

The first line contains an integer $n$ ($1 \le n \le 100\,000$) — the number of sticks Alexey got as a present.

The second line contains $n$ integers $a_1, \ldots, a_n$ ($1 \le a_i \le 10\,000$) — the lengths of the sticks.


-----Output-----

Print one integer — the square of the largest possible distance from $(0, 0)$ to the tree end.


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

Output
26
Input
4
1 1 2 2

Output
20


-----Note-----

The following pictures show optimal trees for example tests. The squared distance in the first example equals $5 \cdot 5 + 1 \cdot 1 = 26$, and in the second example $4 \cdot 4 + 2 \cdot 2 = 20$.

 [Image] 

 [Image]
user: Misha was interested in water delivery from childhood. That's why his mother sent him to the annual Innovative Olympiad in Irrigation (IOI). Pupils from all Berland compete there demonstrating their skills in watering. It is extremely expensive to host such an olympiad, so after the first $n$ olympiads the organizers introduced the following rule of the host city selection.

The host cities of the olympiads are selected in the following way. There are $m$ cities in Berland wishing to host the olympiad, they are numbered from $1$ to $m$. The host city of each next olympiad is determined as the city that hosted the olympiad the smallest number of times before. If there are several such cities, the city with the smallest index is selected among them.

Misha's mother is interested where the olympiad will be held in some specific years. The only information she knows is the above selection rule and the host cities of the first $n$ olympiads. Help her and if you succeed, she will ask Misha to avoid flooding your house.


-----Input-----

The first line contains three integers $n$, $m$ and $q$ ($1 \leq n, m, q \leq 500\,000$) — the number of olympiads before the rule was introduced, the number of cities in Berland wishing to host the olympiad, and the number of years Misha's mother is interested in, respectively.

The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq m$), where $a_i$ denotes the city which hosted the olympiad in the $i$-th year. Note that before the rule was introduced the host city was chosen arbitrarily.

Each of the next $q$ lines contains an integer $k_i$ ($n + 1 \leq k_i \leq 10^{18}$) — the year number Misha's mother is interested in host city in.


-----Output-----

Print $q$ integers. The $i$-th of them should be the city the olympiad will be hosted in the year $k_i$.


-----Examples-----
Input
6 4 10
3 1 1 1 2 2
7
8
9
10
11
12
13
14
15
16

Output
4
3
4
2
3
4
1
2
3
4

Input
4 5 4
4 4 5 1
15
9
13
6

Output
5
3
3
3



-----Note-----

In the first example Misha's mother is interested in the first $10$ years after the rule was introduced. The host cities these years are 4, 3, 4, 2, 3, 4, 1, 2, 3, 4.

In the second example the host cities after the new city is introduced are 2, 3, 1, 2, 3, 5, 1, 2, 3, 4, 5, 1.
user: You got a box with a combination lock. The lock has a display showing n digits. There are two buttons on the box, each button changes digits on the display. You have quickly discovered that the first button adds 1 to all the digits (all digits 9 become digits 0), and the second button shifts all the digits on the display one position to the right (the last digit becomes the first one). For example, if the display is currently showing number 579, then if we push the first button, the display will show 680, and if after that we push the second button, the display will show 068.

You know that the lock will open if the display is showing the smallest possible number that can be obtained by pushing the buttons in some order. The leading zeros are ignored while comparing numbers. Now your task is to find the desired number.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 1000) — the number of digits on the display.

The second line contains n digits — the initial state of the display.


-----Output-----

Print a single line containing n digits — the desired state of the display containing the smallest possible number.


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

Output
024

Input
4
2014

Output
0142