The 2018 World Cup will be hosted in Russia. 32 national teams will be divided into 8 groups. Each group consists of 4 teams. In group matches, each pair (unordered) of teams in the group will have a match. Top 2 teams with the highest score in each group will advance to eighth-finals. Winners of each eighth-final will advance to quarter-finals. Then, the winners of each quarter-final will advance to semi-finals. Eventually, the World Champion will be the winner of the World Final which is played between the two winners of the semi-finals.

Each match is labeled with a match ID sequenced from 1 to 63, with group matches followed by eighth-final matches followed by quarter-final matches followed by semi-finals matches and finally the final match.

Zhuojie is going to watch the 2018 World Cup. Since the World Champion of ACM-ICPC is very rich, he decides to spend 0.01% of his daily salary to buy tickets. However, there are only match IDs on the tickets and the prices are missing. Can you calculate how much Google pays Zhuojie every workday? Note that Zhuojie can buy multiple tickets for one match.

Aori is very careless so she is always making troubles. One day she does it again, with N big troubles! But this time she seems to be at ease because she has found M Inklings to take all the blames. Each trouble can be measured by a severity number a_i. Each trouble needs at least one Inkling to take the blame, and each Inkling can help Aori to take the blame for exactly one trouble. If two or more Inklings take the same trouble, they will take this blame together and discuss how to divide this trouble into.. some trivial things.. to reduce the pressure on each Inkling, as long as the total severity on Inklings is equal to the severity of this trouble.

Inklings are so warm so that Aori wants to think a way to let the variance of severity on each Inkling to be minimal. Could you help Aori make her scapegoats?

Formally, the variance of variables is the expectation of the squared deviation of a variable from its mean:

One year ago, Mr. Ang joined a great company and he rented a house on the same street as the company. The company is so great that Mr. Ang doesn't need to punch in and out. He can have a good sleep and gets up at any time.

Every day, he walks along the street, goes through N traffic lights numbered 1, 2, 3, ..., N and arrives the company. It takes Mr. Ang S₀ seconds from the house to first traffic light. S_i seconds from traffic light i to traffic light i + 1 and S_N seconds from N^th traffic light to company. The time spent on the way to company depends on the state of traffic lights.

Mr. Ang got interested in the traffic lights and hacked into the system. After reading the code, he found that for traffic light i on his way, it stays A_i seconds green and then stays B_i seconds red and repeats. He also found that for all traffic lights, A_i + B_i are the same. He can modify the code to set different offsets OFF_i for the traffic lights. Formally, Mr. Ang can set the offsets for the traffic lights to OFF_i so that for each traffic light, Mr. Ang can go through it in time range [OFF_i + k × (A_i + B_i), OFF_i + k × (A_i + B_i) + A_i) and must wait in time range [OFF_i + k × (A_i + B_i) + A_i, OFF_i + (k + 1) × (A_i + B_i)) for all integers k.

Now Mr. Ang would like to make his commuting time from house to company as short as possible in the worst case. Find out the minimal time in second.

Mr. Panda likes playing with numbers. One day he picked up a number 3612 and found it's interesting. 3612 can be divided into 3 numbers 3, 6 and 12 which forms an integer geometric sequence.

An integer geometric sequence is a sequence of at least 3 positive integer numbers a₀, a₁, ..., a_n - 1, also there is a positive number D (D > 1) that for each i(0 ≤ i < n - 1), a_i × D = a_i + 1.

Mr. Panda named this kind of numbers "Happy Number". He also announced that leading zeros are forbidden, which means there should be no extra zeros before the numbers. Now Mr. Panda would like to know how many Happy Numbers are between L and R inclusive.

Do you like puzzles, fruits and the notion of crossing a snake with a bird for no good reason? If the answer to at least one of those questions is yes, then Snakebird might be the game for you. Solve your way through this head-scratcher of a puzzle game and help the snakebirds sate their hunger.

The game starts with a board of M × N cells, at the beginning each cell is one of the following types.

• 'R', 'G', 'B': Your snakebirds' head. You'll have at least 1 snakebird and at most 3 snakebirds on the board. Once you are moving a snakebird, other snakebirds are treat as obstacles. That means you can not enter a cell that is occupied by other snakebirds.
• '>', '<', '^', 'v': Your snakebirds' body is pointing to another body that is closer to the head. These 4 types are pointing right, left, up, down respective. It's guaranteed that each head/body is pointed by exactly one other body except the last one. It's also guaranteed that each body is pointing to a head/body.
• '.': Empty cell. Your snakebirds can enter empty cells. When a snakebird enters an empty cell, it's head goes into this cell and all it's other bodies go into the position of previous head/body. This action finishes instantly.
• '#': Obstacle. Your snakebirds can not enter obstacles, but if any piece of the snakebird is one cell above the obstacle, the obstacle supports the snakebird and the snakebird will stop falling.
• '|': Spike. Your snakebirds can either enter spikes or falling into the spikes. However, if this happened, the snakebird dies.
• '@': Fruit. Your snakebirds can enter the cell of fruit. When a snakebird enters a cell of fruit, the fruit disappears and the cell becomes an empty cell. Meanwhile, all head/body of the snakebird stay at the position and the snakebird has a new head in the cell of the fruit. The previous head becomes a body connecting with the new head. But when snakebird is falling the fruit is treated as an obstacle even the head of any snakebirds falling towards the fruit.
• 'X': Exit. There is exactly 1 exit on the board. Before all the fruits disappear, the exit is inactive and just like an empty cell. After ALL the fruits disappear, anytime a snakebird's head is in the Exit cell, the snakebird disappears and goes into heaven. Even if the snakebird is falling. If a snakebird falls on a spike or falls out of the board while it's head falls into the Exit cell, it dead before going to heaven. :(

On each move, you can select one of the snakebirds, and move it's head to one of the adjacent cells(four directions) to enter an empty/fruit cell. After each move, something magic is happening, your snakebirds are subject to gravity, which means all snakebirds without support start falling until they land on some obstacles(or other snakebirds with support) or dead. Falling on spike or falling out of the board causes dead. The shape of the snakebird doesn't change during the falling.

It's guaranteed that nothing is going to fall at the beginning.

To help Redbird, Greenbird and Bluebird win the game, you need to send all snakebirds to heaven alive. Find out the minimal number of moves needed.

Given a positive integer M that consists of k digits in decimal notation without leading zeros, a 'digit rotation' of M means a number that is generated by swapping the first j digits and the rest (k - j) digits on M, for any j (0 ≤ j < k). For example, both 231 and 312 are digit rotations of 123, and neither 321 nor 132 is.

A positive integer G is a good number if any digit rotation of G does not exceed G.

Given a positive integer N, return the largest good number that does not exceed N.

There are N binary images numbered from 0 to N - 1. Each image contains M pixels numbered from 0 to M - 1. Each pixel is either black or white. Images are pairwise different by at least one pixel.

Now there are some queries. Each query contains a subset of these images. For each query, you want to find a set of pixels that can distinguish every pair of images in it. Two images can be distinguished from each other by a given set of pixels if they have different pixel values in at least one of the given pixels. The number of pixels selected should be less than the number of images in each query.

Mrs. Panda’s birthday is coming. Mr. Panda wants to compose a song as gift for her birthday.

It is known that Mrs. Panda does not like a song if and only if its lyrics contain X vowels in a row, or Y consonants in a row (Otherwise, Mrs. Panda likes the song). The letters 'a', 'e', 'i', 'o', 'u' are vowels, and all others are consonants.

Though Mr. Panda is a gifted singer, he is bad at composing lyrics. Mr. Panda wants the song to be special. Thus, he searched Google for a template for lyrics of the song.

The template consists of lowercase English letters and possibly question marks. For example, "happybirthday" (without quotes, the same below), "????ybirthday" are valid templates but neither "happy birthday" nor "HappyBirthday" is. Mr. Panda needs to substitute all the question marks with lowercase English letters so that it becomes actual lyrics of the song.

Mr. Panda wants to give a surprise to Mrs. Panda. So, Mr. Panda hopes to compose not only a song from the template that Mrs. Panda likes but also a song from the same template that Mrs. Panda dislikes.

Because Mr. Panda is really bad at composing lyrics, even with a template, the task has confused him for days. Luckily, Mr. Panda knows you are in the contest and wants to ask you for help.

For a given template, output either "DISLIKE" (without quotes, the same below) if Mrs. Panda dislikes all the songs that are generated from the template (that means you cannot substitute letters for question marks so that Mrs. Panda likes the song), "LIKE" if Mrs. Panda likes all the songs that are generated from the template, or "SURPRISE" if Mr. Panda can compose a song Mrs. Panda likes and another song Mrs. Panda dislikes.

PLAYERUNKNOWN'S BATTLEGROUNDS (PUBG, also known as "Chicken Dinner") is the most popular survival shooter game in recent months. Players are dropped into a wide, open area, and they must fight with each other until the last person survives. Specifically, there is a shrinking circle called safe area in the battlefield, while players outside this area will suffer continued damage, which forces them to confront each other and creates chances of skirmish.

Some players are particularly stupid, so they became users of the WG company. But recently, WG company often receive complaints from users that they often die outside the safe area. After carefully study, WG company found that their users are too stupid to know how to run into the safe area. Therefore, they decided to assist their users to complete this action.

After creating a coordinate system on the map, the player is at (x₀, y₀) point at moment 0, with movement speed v. At this moment, there is a circle C₁ with radius of r₁ and center at (x₁, y₁) indicating the safe area now. And players outside the safe area will get d₁ continued damage per unit of time. The safe area will start to shrink at time t₁ and becomes a smaller circle C₂ at time t₂, whose center is (x₂, y₂) and has radius r₂. Since then, players outside the safe area will get d₂ damage per unit of time.

C₂ is strictly in C₁, and the change of circle radius and the movement of circle center are at a constant speed. However, damages outside the safe area will change from d₁ to d₂ instantly at t₂.

Your mission is to calculate the minimum damage the player incurs from the moment 0 till he/she reaches the final safe area C₂ if the player moves optimally.

A straight is a poker hand containing five cards of sequential rank, not necessarily to be the same suit. For example, a hand containing 7 club, 6 spade, 5 spade, 4 heart and 3 diamond forms a straight. In this problem, we extend the definition of a straight to allow 3 to 5 cards of sequential rank. Hence a hand containing K spade, Q club, and J heart is also a straight.

Mr. Panda is playing a poker game called Straight Master. The game uses a large deck of card that has N ranks from 1 to N. The rule of the game is simple: split the cards in Mr. Panda's hand into several straights of length from 3 to 5.

Now given a hand of cards, can you help Mr. Panda to determine if it is possible to split the cards into straights?

The God of Sheep plays an RPG game recently. The game has a level system that records a player's level with a pair of positive integers A and B where A is the major level and B is the minor level. For each major level k, you have to reach minor level L_k in order to upgrade to the next level k + 1. Different major levels may have different number of minor levels. For example, the God of Sheep is currently on level 3-4, and level 3 contains 4 minor levels: 3-1, 3-2, 3-3, and 3-4. Once the God of Sheep upgrades, he will be on level 4-1.

The God of Sheep has work to do now. Countless sheep are suffering in slaughter houses, woolsheds, and dairy farms. The God of Sheep has to rescue his fellow sheep citizens. He will be busy with the rescue plan for a couple of days and meanwhile the level of the game will be downgraded each day as a penalty. The downgrade penalty works like this: with each day the God of Sheep not playing the game, his level A-B will firstly be transformed to A minor levels (with minor level B discarded), and then be cast to an equivalent - pair as his new level. For example, suppose both level 1 and level 2 have 2 minor levels, and the God of Sheep is currently on level 3-3. For the first day of his absence, the level will become 2-1, the second day the level will become 1-2, the third day the level will become 1-1, and from the third day on the level will keep the same level as 1-1.

The God of Sheep wonders which level will he be when he comes back from the rescue?

Mr. Panda and Mr. Sheep are playing a game on a 1 × N game board. Initially, all the cells are empty. Mr. Panda and Mr. Sheep take alternate moves and Mr.Panda moves first.

On each move, a player must fill an 'S' or 'O' into an empty cell. After the move, if there are 3 consecutive cells from left to right form the word "SOS", the player wins the game and the game finished.

If the board gets filled up without SOS appearing consecutively, no one wins the game, the game end with draw.

Now, if both Mr. Panda and Mr. Sheep play optimally, find out the result of the game.

It is said that a dormitory with 6 persons has 7 chat groups ^_^. But the number can be even larger: since every 3 or more persons could make a chat group, there can be 42 different chat groups.

Given N persons in a dormitory, and every K or more persons could make a chat group, how many different chat groups could there be?