Lately Teodoro has been working a lot, solving tons of problems. Now he thinks that he needs some well deserved rest and decided to go to a bath house to take a nice relaxing bath.

Teodoro is very demanding and wants the temperature of the water to be exactly X degrees celsius. The bath house has N taps of water, each with a specific water temperature of a_i degrees celsius. He can open multiple taps to get the exact temperature that he wants by controlling the proportion of water coming out of each tap.

For example, imagine Teodoro opened two taps: the first tap has water at 50 degrees celsius and the second tap has water at 75 degrees celsius. He opened the taps so that there is four times more water coming out of the first tap than the second tap. The resulting temperature r can be calculated as:

Notice that the resulting temperature will always be a weighted mean of the water temperatures of the open taps.

The amount of money that Teodoro will pay at the bath house depends on how many different taps he opens and Teodoro doesn't have much money to spend, so he wants to know what is the minimum number of taps that he has to open to get the desired temperature.

Nicoleta is a very rich and lazy man. He lives in a huge mansion with his sister Marge. Their mansion is perfectly rectangular and has no inner walls. They made it that way so Nicoleta wouldn't need to open doors and avoid walls.

Last night, he invited some friends to play games at his mansion and they made a big mess. Marge is furious about it and demanded that he cleans everything up today.

There are N dirty spots on the mansion's floor and Nicoleta tried to cover them with M expensive rectangular rugs. Each dirty spot on the floor is represented by a point and each rug is represented by a rectangle.

Marge is used to having all rugs parallel to the walls. Nicoleta made sure that no rug is rotated so that she doesn't notice. However, he might have left some rugs overlapping because he is lazy.

He asked you to double check his "cleaning" by counting how many rugs are covering each spot. A rug is covering a spot if the spot is strictly inside the rug's rectangle.

Marge is the newest member of GEMA, a programming competition study group at her university. One of the first things she did as a new member was to look at the last year's regionals scoreboard to see how well the team representing her university performed. Looking at it, she noticed that she had no idea how the teams were ranked in the scoreboard. After searching on the internet she found the following text in the rules section of the ACM-ICPC website, describing how teams are ranked in the scoreboard:

"Teams are ranked according to the most problems solved, ... teams who solve the same number of problems are ranked by least total time. The total time is the sum of the time consumed for each problem solved. The time consumed for a solved problem is the time elapsed from the beginning of the contest to the submittal of the accepted run plus 20 penalty minutes for every rejected run for that problem regardless of submittal time. There is no time consumed for a problem that is not solved."

Marge already knows that ACM-ICPC contests have a duration of 300 minutes and, if at any moment there are multiple teams tied for the first position (same number of problems solved and same total time), she considers that all those teams are leading the scoreboard at the same time.

She found the list of submissions of the contest and now she is interested in finding out the total amount of time in minutes that her university's team was leading the scoreboard.

Joaozao is a famous digit maker in the city of Sao Carlos. He owns a shop downtown where he receives orders to create numbers. Nicoleta, his friend and a very recent hire, is trying to learn this fancy art of digit making.

Joaozao is specialized in making numbers in base B. A number in base B is a sequence of digits written in the following way:

Joaozao received an order to build an n-digit number in base B. It is a lot of work for one day, so he decided to ask Nicoleta, who is still learning, to help him.

The process of building the number is the following: First Joaozao creates 2n digits in base B. After that, Joaozao gives pairs of digits to Nicoleta, one after the other. As Nicoleta receives them, he adds these two digits together and takes the remainder of the division by B, creating a new digit z. Finally, Nicoleta attaches z to the beginning of the number they are building, making z its most significant digit. After n steps, they will have an n-digit number written in base B.

Joaozao has already created 2n digits in base B and they will soon start the next step of the process. They are wondering what is the largest number they can build (the larger the number, the more valuable it is). Nicoleta really wants to impress Joaozao, so he asked you to help him with this task.

Danfsk bought some sheep and wants to protect them from wolves. He had the brilliant idea of building two convex fences, one strictly inside the other, and keeping all sheep inside the inner fence. This way, the sheep would have a second layer of protection from the wolves.

He hired Tomask, a famous fence architect, to design two fences for him. After finishing his project, Tomask gave Danfsk two pieces of paper, each containing the coordinates of the poles of a convex fence.

Tomask is also famous for miscalculations on his projects, so, before paying Tomask and starting building the fences, Danfsk wants to check if one convex fence is really strictly inside the other in Tomask's project. He asked you to help him with this task.

Marge is already preparing for Christmas and bought a beautiful tree, decorated with shiny ornaments. Her Christmas tree can be represented as a complete binary tree composed of N nodes, numbered from 1 to N and rooted on node 1. Each node has an integer value associated to it, representing its shininess.

The shininess of the h - th level of the tree is the sum of the shininess of all the nodes with depth h and the shininess of the tree is the largest value of shininess of its levels.

Nicoleta has a crush on a girl and wants to give her a part of Marge's beautiful tree. To do so, he will choose a node u and give his crush the subtree rooted at node u, including u. However, he doesn't want to get in (too much) trouble with Marge, so he will consider some candidates before making the cut.

Nicoleta has M candidate nodes to be the root of the cut subtree. For each candidate, Nicoleta wants to know what is the value of shininess of the remaining tree.

Teodoro just moved to Canada. He is having a hard time there as the cost of living is higher than he expected. He is short on money so he decided to eat a string, as they are cheaper than food. He knows exactly how hungry he is, so he will buy a string with exactly K letters.

Teodoro went to a string store and saw that the price of a string depends on which letters are adjacent. For example, the price of the string "bca" is equal to the cost of putting "c" after "b" and "a" after "c". The costs of adjacent letters are given in a 26 × 26 matrix P, in which p_i, j corresponds to the cost of putting the j-th letter of the alphabet after the i-th letter of the alphabet, e.g., p_3, 7 is the cost of putting "g" after "c". Notice that the cost of putting i after j may not be the same as putting j after i, that is, p_i, j may be different from p_j, i.

Teodoro wants to order a string of size K with the minimum possible price. He is so hungry that he can barely think. Please help him find the cheapest string of size K.

Joaozao and Nicoleta are planning to buy some pies at the local market. There are K different types of pies and Joaozao only buys pies of the types that are on his list of preferred pie types. The same goes for Nicoleta, who only buys pies of the types that are on his list of preferred pie types. It's guaranteed that every type of pie appears on at least one list of preferences.

The local market is doing a special pie sale. Because of this, all N pies are lined up in a row. The first pie in the row is of type p₁, the second pie is of type p₂ and so on until the N-th pie that is of type p_N. It is guaranteed that the market sells all types of pies (i.e. each one of the K types of pies will appear at least once in this row). The special promotion of this sale was: if the same person buys pie i and pie i + 1, where i is the position of the pie in the row, this person gets g_i candies.

Pies of the same type cannot be bought by different people (i.e. if Joaozao buys one pie of type t, then he has to buy all other pies of the same type t).

Joaozao and Nicoleta decided they will buy all N pies in the row and they want to maximize the total amount of candies they will earn. Given the lists of preferences for each one of them, the type of the pies in the row and the amount of candies that is earned for each pair of consecutive pies, can you tell what is the maximum total amount of candies they can get?

The total amount of candies is the sum of the candies earned by each of them.

Sancho is a matrix lover. Today he decided to play with a square matrix M with N rows and N columns. Every cell i, j of this matrix contains either 0 or 1.

From this matrix M he created another matrix A. Every cell i, j in this new matrix A contains the sum of the values of the cells in M that are in row i or column j. The element in the cell i, j of the matrix M should be added only once. Formally:

Unfortunately, Sancho lost the original matrix M and now, having only matrix A, he wonders what is the number of matrices M, such that matrix A can be created from M.

Sancho loves geometry. And he loves triangles even more, to the point of developing his own metric of beauty for triangles. In his metric, the beauty of a triangle is calculated by subtracting the length of the largest side from the sum of the lengths of the other two sides.

During weekends, Sancho likes to walk by the beach looking for straight sticks to build his triangles. He has already found 2 sticks and he's very optimistic about the triangle he's going to build.

He wants to know what should be the length of the third stick so that the beauty of his triangle is maximized. Help him with this task!

When building teams for programming competitions, it is a good idea to team up people that are good at different topics. For instance, it would be a good idea to team up someone who is good at graph problems and bad at geometry problems with someone who is good at geometry problems but bad at graph problems.

GEMA is a programming competition study group with N members. GEMA coaches are interested in counting the number of different good teams that can be created. A good team is composed of 2 members and each member is good at at least one topic that his teammate isn't good at. Two teams are considered different if at least one member is present in one team but not in the other.

GEMA coaches are only considering the M most important topics, and they know, for each member, which topics they are good at, and which topics they are bad at.