Description

Elfnt just walked into an all-you-can-eat vegan buffet, represented by an grid. Each cell holds a food tray with a certain amount of fresh salad leaves. Initially, Elfnt starts at position (0-indexed) and is eager to eat as much as possible!

Elfnt can smell trays within a Manhattan distance of at most from his current position. He greedily eats according to the following rules:

1. Elfnt completely cleans out the salad tray at his current position, adding its leaves to his total. The amount of leaves at this cell then becomes 0 (indicating an empty plate).
2. He sniffs around and moves to the tray within Manhattan distance that has the greatest amount of leaves. If all reachable trays within distance contain 0 leaves, Elfnt stops moving and eating immediately.

Note:

• The Manhattan distance between two cells and is defined as .

Input

The first line contains three integers , , and — the number of rows, the number of columns, and the maximum Manhattan distance Elfnt can smell.
The next lines each contain integers, representing the initial amount of leaves on each tray.
The last line contains two integers and , representing Elfnt's starting row and column coordinates.

Constraints

• The initial amount of leaves on any tray satisfies .
• All non-zero leaf amounts are guaranteed to be distinct (i.e., except for trays with 0 leaves, all leaf values across the buffet are unique).

Output

Output a single integer representing the total amount of salad leaves Elfnt consumes before he stops, followed by a new line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Elfnt and his family (a total of elephants) are claiming their own territories. We can represent the land as a 1D coordinate line. Each elephant chooses a continuous segment as its territory, starting from position to (inclusive interval ).

An elephant A's territory completely contains elephant B's territory if and .

Your task is to analyze the overlapping territories. For each elephant, determine if its territory contains at least one other elephant's territory, and if its territory is contained by at least one other elephant's territory.

Input

The first line contains a single integer — the number of elephants.
The following lines each contain two integers and , representing the starting and ending points of an elephant's territory.
(Note: The elephants are numbered from to in the order they appear in the input).

Constraints

• All given territories are guaranteed to be distinct.

Output

The first line should contain integers. The -th integer should be 1 if the -th elephant's territory completely contains at least one other territory, and 0 otherwise.
The second line should contain integers. The -th integer should be 1 if the -th elephant's territory is completely contained by at least one other territory, and 0 otherwise.

For both lines, consecutive integers must be separated by a space. There must be no space after the last integer of each line, and each line must end with a newline.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

RedCapeFlyingCat is standing at coordinate on a number line and wants to reach the goal at coordinate .

There is a wall at coordinate . At first, RedCapeFlyingCat cannot pass through coordinate . There is also a hammer at coordinate : once RedCapeFlyingCat arrives at coordinate , the hammer is picked up, and from then on the wall can be broken and passed through.

Determine whether RedCapeFlyingCat can reach the goal. If so, find the minimum total distance that has to be traveled.

Explanation

In the sample test case, , , and . The wall is farther away than the goal, so it is not in the way: RedCapeFlyingCat goes straight from to . The total distance is .

Two more examples (they are not given as sample test cases):

• , , : the wall blocks the way to the goal. RedCapeFlyingCat first goes from to to pick up the hammer (distance ), then goes from to , breaking the wall on the way (distance ). The total distance is .
• , , : the wall blocks the way to the goal, and it also blocks the way to the hammer. The goal cannot be reached, so the answer is -1.

Input

Three lines, each with one integer:

• Line 1: , the coordinate of the goal
• Line 2: , the coordinate of the wall
• Line 3: , the coordinate of the hammer

Constraints

• , and
• , , and are distinct
• All input values are integers

Output

One line containing one integer: the minimum total distance RedCapeFlyingCat has to travel to reach the goal.

If the goal cannot be reached, output -1.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

RedCapeFlyingCat likes to play with numbers by reading them backwards.

For a positive integer , let be the number obtained by writing the decimal digits of in reverse order and dropping any leading zeros. For example, and .

One operation replaces with .

A positive integer is a palindrome if it reads the same forwards and backwards, that is, if .

You are given queries. Each query consists of two integers and . Start with and perform the operation exactly times, even if becomes a palindrome earlier. Report the final value of and whether it is a palindrome.

Explanation

The sample test case has queries.

• , : . The final value is a palindrome.
• , : . The final value is not a palindrome.
• , : is already a palindrome, but the operation is still performed once: , which is a palindrome.
• , : no operation is performed. The final value is a palindrome.

Input

The first line contains one integer , the number of queries.

Each of the next lines contains two integers and , separated by a single space.

Constraints

• All input values are integers

Output

For each query, output one line containing the final value of , followed by a single space, followed by Yes if the final value is a palindrome and No otherwise.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Deep within the Crimson Demon Village lies an ancient sealed ruin, and Megumin has decided to break the seal out of sheer curiosity! Her first attempt, of course, was to blast it with Explosion, which did absolutely nothing. Lying exhausted on the ground afterward (as usual), she finally noticed an inscription carved into the seal: a string consisting of lowercase English letters. Legend says the seal will only open when this inscription is recited in its encrypted form. Help her unlock it by computing the encryption , defined recursively as follows:

• denotes the length of , denotes the empty string, and denotes string concatenation.
• is the middle character of , i.e., the character at index (0-indexed). If is even, is the left one of the two middle characters.
• and are obtained by splitting at :
  • is the substring to the left of .
  • is the substring to the right of .
  • Neither nor contains itself, and either of them may be empty.
• shifts the lowercase letter forward by positions in the alphabet, wrapping around from z back to a (e.g., ). Formally, it is the character whose ASCII code is , where is the ASCII code of a.

For example, if the inscription is :

Enc("quiz") = shift('u', 4) + Enc("q") + Enc("iz")
Enc("q")    = shift('q', 1) + Enc("") + Enc("")  = "r"
Enc("z")    = shift('z', 1) + Enc("") + Enc("")  = "a"   (wraps around from z to a)
Enc("iz")   = shift('i', 2) + Enc("") + Enc("z") = "k" + "" + "a" = "ka"
Enc("quiz") = shift('u', 4) + "r" + "ka" = "y" + "r" + "ka" = "yrka"

Input

A single line containing the string .

Constraints

• consists only of lowercase English letters (a–z).

Subtasks

• Subtask 1 (Testcase 1-5): , and consists only of the letters a through m (so no wrap-around occurs).
• Subtask 2 (Testcase 6-10): No additional constraints.

Output

Output a single line containing the string .

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Megumin knows only one spell, but it is the most powerful one in the world: Explosion. It drains all of her mana, so she can cast it only once a day. Afterward, she collapses on the spot, and Kazuma, her party leader, has to carry her back to the town of Axel.

Lately, the plains outside Axel have been overrun by giant toads. The plains are divided into an grid, and cell contains giant toads.

To make her single daily cast count, Megumin has invented a new version of her beloved spell: the X-plosion. When she targets cell , the blast travels along both diagonals through that cell, all the way to the edges of the plains:

1. The diagonal running from top-left to bottom-right through .
2. The diagonal running from top-right to bottom-left through .

Every giant toad on these two diagonals is blown away. The target cell lies on both diagonals, but its toads can only be blown away once.

Kazuma does not want to carry her home after a disappointing cast, so he has written down candidate target cells to compare. Since Megumin will not cast until he has chosen a target, each candidate is evaluated independently on the original plains. Help him by writing a program that calculates, for each candidate, how many giant toads the X-plosion would blow away.

(Note: The grid is 0-indexed. Cell is in row and column , so the top-left cell is and the bottom-right cell is . Likewise, is the row index and is the column index of the target cell.)

Input

The first line contains two space-separated integers, and , representing the size of the plains and the number of candidate targets, respectively.

The next lines describe the plains. The -th of these lines () contains integers .

The following lines describe the candidates. Each line contains two integers and , representing one candidate target cell .

Constraints

Subtasks

• Subtask 1 (Testcase 1–3): , .
• Subtask 2 (Testcase 4–6): .
• Subtask 3 (Testcase 7–10): No additional constraints.

Output

For each of the candidates, output a single integer on a new line: the number of giant toads that the X-plosion would blow away.

Sample Explanation

For the first candidate , the X-plosion would hit the cells marked with square brackets:

[1]  2  [3]  4
 5  [6]  7   8
[9]  1  [2]  3
 4   5   6  [7]

The target cell lies on both diagonals, but its toads are counted only once, so the answer is .

For the second candidate , the X-plosion would hit the marked cells:

 1   2  [3]  4
 5  [6]  7  [8]
[9]  1   2   3
 4   5   6   7

The answer is . The first candidate's X-plosion would also hit cells , , and , but since each candidate is evaluated independently, their toads are counted again.

Sample Input  Download

Sample Output  Download

Tags

Discuss