There is a piece of a chessboard of strange shape consisting of ten squares. On the board, there are two black knights and two white knights. The task is to swap them (that is, to make the black knights move to the places of the white ones, and vice versa).
Recall that a knight moves in an "L" shape — two squares horizontally and one square vertically, or one square vertically and two squares horizontally. A move can only be made to an empty square on the board.
To submit your solution, click the "Submit code" link (above the problem statement). In the source code field, enter the found moves. Each move should be entered on a separate line in the form of two numbers separated by a space — the number of the starting and ending square (the numbering of the squares is shown in the picture). Do not write anything else. When submitting the solution, select the PHP language (you do not need to know this language, it is just a feature of the system).
A complete solution will receive 100 points, a solution in which three knights are correctly placed will receive 75 points, two knights will receive 50 points, and one knight will receive 25 points. In all cases, all moves must be correct (that is, there must be a knight in the starting square, and the ending square must be empty).
There is a two-way circular road around the city with a length of $$$L$$$. One point on the road is chosen as the starting point (zero coordinate).
Along the road, there are $$$N$$$ fuel stations. The owner wants to build a fuel storage facility near one of the stations in such a way that the sum of the distances from the storage to the remaining stations is minimized. Find the optimal location for the storage facility.
The first line of the input contains an integer $$$L$$$ ($$$1 \le L \le 10^9$$$) — the length of the road.
The second line contains an integer $$$N$$$ ($$$1 \le N \le 2 \cdot 10^5$$$) — the number of fuel stations.
In the following $$$N$$$ lines, there are $$$N$$$ distinct integers $$$x_1$$$, $$$x_2$$$, ..., $$$x_N$$$ in increasing order, where $$$x_i$$$ is the coordinate of the $$$i$$$-th station, i.e. the distance from the starting point to the $$$i$$$-th station when moving clockwise ($$$0 \le x_i \lt L$$$).
Output a single integer from 1 to $$$N$$$ — the number of the fuel station near which the storage facility should be built. If there are multiple correct answers, output any.
Subtask 1 (up to 40 points): $$$L \le 1000$$$, $$$N \le 1000$$$.
Subtask 2 (up to 60 points): no additional constraints.
83145
2
Illustration for the example:
Note that the sum of distances may not fit into a 32-bit data type. It is recommended to use a 64-bit data type, such as the long long type in C++, the int64 type in Pascal, or the long type in Java and C#. Python automatically handles integers of any length.
On a chessboard of size $$$N$$$ x $$$N$$$, there are $$$K$$$ bishops. Recall that a bishop is a piece that can move to any number of empty squares diagonally in one of four directions (up-right, up-left, down-right, and down-left) in a single move.
Find an empty square such that it is under attack by the maximum number of bishops (i.e., the maximum number of bishops can reach this square in one move).
The first line of input contains an integer $$$N$$$ ($$$2 \le N \le 10^9$$$).
The second line contains an integer $$$K$$$ ($$$1 \le K \le min(1000, N^2-1)$$$).
The next $$$K$$$ lines contain pairs of integers $$$x_i$$$, $$$y_i$$$ separated by spaces — the coordinates of the bishops ($$$1 \le x_i, y_i \le n$$$). No two pairs of coordinates are the same.
Output two integers — the coordinates of the found square (first the horizontal coordinate, then the vertical coordinate). If there are multiple correct answers, output any.
Subtask 1 (up to 30 points): $$$N \le 100$$$.
Subtask 2 (up to 30 points): $$$K = 2$$$.
Subtask 3 (up to 40 points): no additional constraints.
431 23 24 1
2 3
Below is a illustration for the example. One of the two possible target squares is shaded gray. It is under attack by two bishops (the third bishop cannot reach it because another bishop is blocking the way). Note that the answer "2 1" is also correct.
In the qualifying round of the olympiad, you solved the problem "Good Pairs." Recall that an unordered pair of natural numbers is called good if one of them divides the other.
While preparing the problem from the qualifying round, the jury encountered the following issue. To verify the correctness of the solution, it is necessary to quickly find the number of good pairs that can be formed from the numbers output by the participant's program. The jury managed to solve this problem, but can you?
More formally: you are given $$$n$$$ natural numbers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$. Find the number of such pairs of indices $$$i$$$, $$$j$$$, where $$$i \lt j$$$, such that $$$a_i$$$ divides $$$a_j$$$ or $$$a_j$$$ divides $$$a_i$$$.
The first line of input contains a natural number $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of numbers.
In the next $$$n$$$ lines, the integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ are given, where $$$1 \le a_i \le 10^6$$$.
Output a single integer — the number of good pairs that can be formed from the input numbers.
Subtask 1 (up to 20 points): $$$n \le 1000$$$.
Subtask 2 (up to 40 points): all $$$a_i$$$ do not exceed 1000.
Subtask 3 (up to 40 points): there are no additional constraints.
32510
2
211
1
Note that the answer may exceed the possible value of a 32-bit integer variable. Therefore, it is necessary to use a 64-bit integer data type (type int64 in Pascal, type long long in C++, type long in Java and C#). In Python, no additional actions are required.
Write a program to find the smallest natural (positive integer) number so that this number, written in Russian words in the nominative case, would have a length of exactly $$$k$$$ characters excluding spaces.
An integer $$$k$$$ ($$$1 \le k \le 165$$$).
Output the integer found. If there is no answer, output 0.
There are 100 tests in this problem. One point is awarded for passing each test.
150
11488488484484
The number in the example is written in Russian as: «одиннадцать триллионов четыреста восемьдесят восемь миллиардов четыреста восемьдесят восемь миллионов четыреста восемьдесят четыре тысячи четыреста восемьдесят четыре». This string contains 150 characters excluding spaces.
In this problem, it is assumed that for numbers greater than one, the word "один" or "одна" is not written at the beginning of the number, but is written elsewhere. For example, the number 1001001 will be written as "миллион одна тысяча один".
Participants writing in C++ are advised not to use string constants in Russian in their program, as the functions «length» and «strlen» on the server may incorrectly calculate the length of strings with Russian letters (due to Unicode encoding).