There are two popular formats for representing a date: day/month/year or month/day/year. For example, today can be represented as 15/8/2017 or 8/15/2017.

Sometimes (like on today), using one way or another should pose no confusion — it is immediately understood that the date is the 15th of August. On other days, however, the two representations may be interpreted as two different valid dates. For example, the 7th of August may be misinterpreted as the 8th of July, since both can be represented as 7/8/2017 (or 8/7/2017).

We say a date (D, M, Y) is ambiguous if D/M/Y and M/D/Y, when both interpreted in the day/month/year format, are different valid dates. For example, (7, 8, 2017) and (8, 7, 2017) are ambiguous, while (15, 8, 2017) and (10, 10, 2017) are not.

The total number of ambiguous dates in the Gregorian calendar system on any given year is equal to 12 × 11 = 132.

Now, suppose that in a hypothetical calendar system, there are M months, where the i-th month has D[i] days, numbered from 1 to D[i]. Assume that there are no leap years.

You are to carry out a calendar reform, by shuffling the array D[], and your target is to minimize the total number of ambiguous dates in a calendar year. Specifically, you want to find a permutation p[1], p[2], ..., p[M] of integers 1, 2, ..., M, such that the new calendar system, where the i-th month has D[p[i]] days, has the minimal number of ambiguous dates. Output that minimal number.

A year after his bacteria experiment, Jason decided to perform another experiment on a new bacteria specie which evolves in a special way. The initial form of the bacteria can be considered as an undirected tree with N nodes in terms of graph theory. Every hour, an edge (x, y) is built if there exists a node z such that, in the previous hour, there exists edge (x, z) and edge (y, z), but not edge (x, y). The bacteria keep evolving until no more edges can be formed.

The following graph shows a type of bacteria which requires 2 hours to fully evolve:

As it may take months if not years for the bacteria to evolve to its ultimate form, it is impossible for Jason to stay at the laboratory to observe the change of the bacteria throughout the entire process. Therefore, he wants you to calculate the time required for the bacteria to fully evolve, so that he can just get back to the laboratory on time.

To boost contestants' performances in the 20th La Salle - Pui Ching Programming Challenge, the organizers have bought N robots to cheer for them. Each robot is supposed to display cheering slogans, letter by letter.

Unfortunately, due to some technical reasons, the display screen of each robot can only display one fixed character. Therefore, the organizers decided to arrange the robots in a row, thus forming a string of N letters (What a waste!). All letters are in uppercase.

The two hosting schools have abbreviated names LSC and PCMS, as we all know. Which of the two names appear (as a substring) in the string more often?

The Gregorian calendar is internationally the most widely used civil calendar. It is named after Pope Gregory XIII, who introduced it in October 1582.

In the Gregorian calendar, there are 28 days in February in a common year and 29 days in February in a leap year. Year Y is a leap year if and only if Y is a multiple of 400, or Y is a multiple of 4 and is not a multiple of 100.

Percy is curious about the distribution of days of the week of his birthday in his life. By checking the calendar, he quickly finds that in the years between 1999 and 2017 (inclusive), his birthday (in case you do not know, 27 February) appears only twice on both Tuesday and Thursday, three times on each of the other days of the week.

Percy finds counting the distribution of some days in some consecutive years really cool, so he decides to invent a way to quickly count the distribution.

Within 15 minutes, he successfully invented a fast program to do the calculation for years between 1583 and 2 × 10⁹, inclusive. His program can answer 5000 queries in 1 second. However, he is not sure if the program works correctly, so he needs your help. Your task is simple, write your own program to do the calculation, so that Percy can check his program's correctness by comparing the outputs of different queries with your program.

In this problem, please assume the definition of leap years mentioned above is true for all years between 1583 and 2 × 10⁹, inclusive.

The magician Alice is playing a game. Alice has N balls in a row, consists of red balls and blue balls. For convenience, the balls are numbered 1 to N from left to right. Her goal is to transform all balls into White by casting magic spells.

In a single spell, Alice can choose exactly R red balls and B blue balls at the same time, and then cast a spell on them, so all these R + B chosen balls will become white balls. However, there is a restriction: As some magical power may remains in the white balls, Alice cannot perform spells when there exists at least one white ball located between the leftmost chosen ball and the rightmost chosen ball.

For instance, if Alice balls 2, 6 and 7 have became white balls by previous spells, she cannot choose the set of balls {3, 8, 9} in a single spell as there exist a white ball numbered 5 between them. Similarly, single spell on balls {1, 3, 4}, {3, 4, 9} or {1, 9, 10} are invalid, while single spell on balls {3, 4, 5} or {8, 9, 10} are valid.

As Alice has spent more than hundred of years to achieve the goal and end up in failures, she is very frustrated. So, she promised that she will teach her magic skills to the one who can solve this frustrating game.

Nothing is more appealing than having an opportunity to learn magic! So you are trying to help Alice to achieve the goal.

Gravitational Tetris is a Tetris variant that individual blocks can freely fall to the bottom. Therefore the game state of Gravitational Tetris can be described by an array of 10 integers, each representing the number of blocks (the height) of the column. The columns are numbered from 1 to 10. For example, the game state below can be described by the array [1, 5, 3, 0, 2, 0, 3, 1, 0, 1].

You are given a valid Gravitation Tetris game state. Your task is to continue to play the game such that all blocks are eliminated. A row will be eliminated when there are 10 blocks in the row.

Since the blocks can freely fall, there are only 8 distinct Tetrominoes (shapes), with all rotations taken into account. The letter below each Tetromino denotes its type and its left-most column. In each move, you should select a Tetromino type and a column number c. For type A, it will fall onto column c. For type B, it will fall onto columns c, c + 1, c + 2 and c + 3. For type C, E and G, it will fall onto columns c and c + 1. For type D, F and H, it will fall onto columns c, c + 1 and c + 2. For example, from the above game state, after choosing type G and column 4, it will become:

You are allowed to use at most 1000 moves and there is no height restriction. Completed rows will be eliminated automatically.

"Hit!" is a popular game in ancient Byteland.

The very first version of the game is quite simple: each player picks up a stone and throws it at a circle drawn on the ground. A player wins if his/her stone lands inside the circle.

After 20 years of practice, Bitman, a young man living in ancient Byteland, has mastered the skill of throwing stones – he can throw a stone at any specific place he wants. With such skill, Bitman plays "Hit!" without losing a single game. He simply targets every stone at the center of the circle!

The King of Hackerland hears the story of Bitman and wants to challenge him with a harder, though still very simple, version of "Hit!".

In each game, two circles which share a positive common area are drawn on the ground. In order to win, the player must throw a stone at the common area of the two circles.

As Bitman had no idea how to target his stone at the common area, he asks for your help. Given the coordinates of the centers and radii of the two circles, please tell Bitman the coordinates of any point he can target at such that he can win the game.

For simplicity, you can consider the landing position of the stone as a single point.

Arya lives in a magical world. You can view it as a number line.

There are N citizens in total. The i-th citizen have his own house in position i with height H_i, Noted that H_i could be non positive, which means their house is actually built beneath the horizon.

Arya is the hand of the king and she thinks that the buildings are a bit out of order. She denote the chaos index of the world as .

Noted that h_i could be equal to zero as the world is magical.

She feels that the current chaos index of the world is too high. So she designs to change the world a bit by using her super power.

She could flip a continuous sequence of building, i.e., she could choose two arbitrary integer L and R, where 1 ≤ L ≤ R ≤ N, and invert the signs of H_i for all L ≤ i ≤ R (positive to negative and vice versa).

As Arya is weak, she would only do this operation exactly once. Arya wants to minimize the chaos index after the operation. Being a good guy, help Arya to find the lowest possible chaos index after exactly flipping one continuous sequence of building.

Alex enjoys eating snacks, in particular candies. Recently he discovered a brand of berry-themed juicy candies, with three flavors: blueberry (B), raspberry (R), and strawberry (S). For brevity, we would, for example, use the term B-candy to refer to blueberry-flavored candy.

Alex has B B-candies, R R-candies, and S S-candies. He now wants to form sequences of candies, such that:

• All Alex's candies are used
• Any two adjacent candies have different flavors

For each candy sequence, there is a string of length (B + R + S) corresponding to it. If the i-th candy in the sequence is strawberry-flavored, for example, then the i-th character of the string would be S. Similarly for blueberry- and raspberry-flavored candies.

Before enjoying the candies, Alex would like to solve the following challenge: among all strings which corresponds to a candy sequence, what is the K-th lexicographically smallest string?

For two strings s[1...L] and t[1...L], s is said to be lexicographically smaller than t, if there exists an index i (1 ≤ i ≤ L), such that s[j] = t[j] for 1 ≤ j < i, and s[i] < t[i]. We naturally use the character relation B  <  R  <  S.

The King of Byteland owns an army of well-trained knights. One day, he decides to attack Hackerland. Hackerland can be described as a grid with N rows and M columns. The cell on the i-th row, j-th column is called cell (i, j) for convenience. The north-west corner is (1, 1) while the south-east corner is (N, M).

In order to win, the Byteland army must occupy all cells with knights. Now, the King of Byteland has carefully planned the attack. The attack can be divided into two phases.

In the first phase, a number of knights are sent to some specific cells of Hackerland.

After the first phase has ended, the second phase begins. In the second phase, The knights will start attacking the land of Hackerland. Their only way to attack is as follows: If at any moment, there are two knights on the same row or the same column, then all unoccupied cells between the two knights will be under attack, and more knights will be immediately sent to occupy these cells. This phase will end when no more cells can be occupied.

Please note that the knights are not allowed to move once they are sent to Hackerland.

In the following graph, the cells (2, 7), (4, 3), (5, 7) and (8, 3) are occupied in the first phase.

When the second phase starts, the cells between (4, 3) and (8, 3), (2, 7) and (5, 7) are under attack, and then occupied by other knights. Afterwards, the cells between (4, 3) and (4, 7), (5, 3) and (5, 7) will also be occupied. The second phase will end after this as no more cells can be occupied.

The attack is currently in the first phase. K cells of Hackerland are already occupied under the command of the King. You, the leader of the knights, are going to send some more knights (possibly none) to some cells of Hackerland of your choice before the second phase starts.

On one hand, you have to send enough knights to ensure that at the end of the war, all cells are occupied. On the other hand, you have to send as few knights as possible to minimize the chance of being discovered by the army of Hackerland. Your task is to find out the minimum number of knights to be sent.