UTPC x WiCS Contest 10-06-23
A. Bread Bonanza
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Baker Sdozen is participating in the grand baking competition known as the "Bread Bonanza." In this exhilarating contest, chefs compete to bake as much bread as possible. Whoever makes the most bread (by weight) wins.

However, due to the limitations of their weighing scale, each measurement only yields a single-digit value. Thus, the clever Baker has decided to weigh their bread piece by piece, ensuring that all the bread gets weighed. To complicate matters further, when recording the weights, Baker Sdozen did not put any spaces between the measurements, resulting in what appears to be a very long number.

Given this resulting long number, help Baker Sdozen calculate the total weight of all the bread by adding up all the digits.

Input

A single integer, with $$$1000$$$ or fewer digits.

Output

Print a single integer, the total weight of all the bread.

Examples
Input
493
Output
16
Input
9383
Output
23
Note

In the first example, $$$4 + 9 + 3 = 16$$$.

In the second example, $$$9 + 3 + 8 + 3 = 23$$$.

B. Trinket Tidying Challenge
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Chef Chomperio is passionate about organizing and tidying up trinkets. Currently, they have $$$N$$$ ($$$1 \leq N \leq 10^5$$$) trinkets to dispose of.

To efficiently manage the trinkets, Chef has trash bags with a limited capacity; each bag can accommodate a maximum of $$$K$$$ ($$$1 \leq K \leq 10^5$$$) pounds of trash. Each trinket has some weight between $$$1$$$ and $$$K$$$ pounds, and the Chef can only throw them away in the order they are presented.

Chef Chomperio wants to minimize the number of trash bags used while efficiently discarding all the trinkets. At all times, Chef can either continue filling the current bag if there is sufficient capacity or throw it away and start with a new bag, but cannot hold on to more than one partially filled bag.

Given the number of trinkets $$$N$$$ as well as the size of trash bags, $$$K$$$, help Chef Chomperio determine the minimum number of trash bags required to tidy the trinkets.

Input

The first line contains two integers, $$$N$$$ $$$(1 \leq N \leq 10^5)$$$ and $$$K$$$ $$$(1 \leq K \leq 10^5)$$$, representing the number of unique trinkets to tidy up and the maximum capacity of a trash bag, respectively.

The second line contains $$$N$$$ integers separated by a single space, representing the sizes of the trinkets in the order Chef needs to discard them. The $$$i$$$-th integer is the weight of the $$$i$$$-th trinket $$$(1 \leq \text{{trinket weight}} \leq K)$$$.

Output

Print a single integer, the minimum number of trash bags Chef Chomperio will use.

Examples
Input
4 3
1 3 1 1
Output
3
Input
2 5
4 5
Output
2
Note

In the first example, we bundle $$$(1)(3)(1, 1)$$$.

In the second example, we bundle $$$(4) (5)$$$.

C. Cooking Class
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Autumn is training to pursue a career as a code chef! In order to learn how to prepare the tastiest bytes to eat, she is going to enter a cooking competition.

Also participating in the competition are $$$N$$$ other competitors of skill levels $$$S_1, S_2, \dots, S_N$$$ whereas Autumn has a current skill level of $$$S_A$$$.

Additionally, Autumn is going to prepare for the competition by attending exactly one of $$$M$$$ different cooking classes. The $$$i$$$th cooking class has an associated value $$$P_i$$$ such that if Autumn attends class $$$i$$$, her new cooking skill level will become $$$S_A + P_i$$$. The rest of the competitors are too cocky and choose not to attend any cooking classes before the competition.

It turns out that the cooking competition involves no luck and is entirely skill-based. As such, a competitor's rank in the competition is directly correlated with their rank. A higher-skilled contestant will always outrank a contestant with a lower skill level, and equally skilled competitors will always tie for the same rank. Knowing that Autumn will attend exactly one of the $$$M$$$ cooking classes, please help her figure out what the best rank she can achieve in the cooking competition is.

Note: The contestant with the highest skill level will be of rank 1. If there are ties, all contestants tied with each other will have the same rank and then the ranking will proceed by skipping the numbers between the tied rank and the sum of the rank and the number of tied contestants (for example, if there are three contestants tied with the highest skill level, they they will all be rank 1, and the next contestant will be rank 4, and so on).

Input

The input will begin with a line containing two space-separated integers, $$$N\ (1 \leq N \leq 2 \cdot 10^5)$$$ and $$$M\ (1 \leq M \leq 2 \cdot 10^5)$$$ denoting the number of contestants other than Autumn and the number of potential cooking classes Autumn may choose from, respectively.

The next line will consist of $$$N + 1$$$ space-separated integers, $$$S_1, S_2, \dots, S_N$$$ and $$$S_A\ (1 \leq S_1, S_2, \dots, S_N, S_A \leq 10^9)$$$, denoting the skill levels of the other contestants as well as Autumn's initial skill level, respectively.

The final line will consist of $$$M$$$ space-separated integers, $$$P_1, P_2, \dots, P_M\ (1 \leq P_1, P_2, \dots, P_M \leq 10^9)$$$, denoting the skill boosts that Autumn will attain from attending each of the respective cooking classes.

Output

The output should consist of exactly one positive integer denoting the best ranking that Autumn can achieve by maximizing her skill level through attending exactly one of the potential cooking classes and boosting her skill level by the respective amount.

Example
Input
5 5
3 3 3 4 5 2
1 2 3 4 5
Output
1
Note

In the sample test case, it would be optimal for Autumn to attend cooking lesson 5 which has an associated skill boost value $$$P_5 = 5$$$ so that her total skill value becomes $$$S_A + P_5 = 2 + 5 = 7$$$. This way, she outranks all of the other competitors in terms of skills, earning her the rank 1 spot.

D. Fractal Pancakes
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Hilbert is lucid dreaming. In his dream, he attempts to use one drop of batter to fry a pancake that fills his entire square pan. Fortunately, he is rational enough to believe there is insufficient batter to do this, so instead he decides to cast a magic spell. The spell consists of $$$n$$$ iterations, where on each iteration the current shape of the pancake will be copied into the four equal regions of the pan, and the bottom two will be rotated 90 degrees inwards. After connecting the four regions together, the resulting transformation can be seen stretching the pancake into progressively smaller segments until it fills up the whole pan. Hilbert is interested in figuring out how many segments there are on the $$$nth$$$ iteration, mod 1000000007.

Input

The input contains one integer $$$1 \leq n\leq 10^5$$$, the number of iterations.

Output

Please print one integer, the number of segments that the pancake contains after iteration $$$n$$$, in mod 1000000007.

Examples
Input
2
Output
13
Input
32
Output
665875208
Note

In the first sample, the pancake starts out like this:

On the first iteration, the pancake fills cells (1,1) to (2,2). We connect cells (2,2) to (2,3) and (2,1) to (3,1) and (4,2) to (4,3). Coordinate (1, 1) here is in the top left, and the coordinates are written in row-column order.

On the second iteration, we again make four copies, and connect cells (4,4) to (4,5) and (4,1) to (5,1) and (4,8) to (5,8).

There are 3 and 13 segments (mod 1e9+7) on the first and second iteration respectively.

E. Dish Ordering
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Meri, the famous prodigy mouse chef, helping to prepare a huge order of $$$n$$$ dishes with the help of her sidekick, Albert Spaghetti.

The menu is rather small, and so each type of dish can be uniquely represented by a single uppercase letter, A-Z. As Meri and Albert put their finishing touches on the dishes, Meri realizes that the dishes are about to be served in the wrong order!

In particular, the current dishes are in the order $$$s_1, s_2, \ldots, s_n$$$, where $$$s_i$$$ signifies that the $$$i$$$th dish is of type $$$s_i$$$. However, the dishes need to be served in the order $$$t_1, t_2, \ldots, t_n$$$.

Meri is too small to move the dishes on her own, so she needs to tell Albert what to do! However, Meri's only form of communication involves tugging on his hair, which is only enough to get him to swap adjacent dishes.

Hurry! The customers are getting antsy, and the dishes need to be sent out as fast as possible. Can you get Meri and Albert to arrange the dishes in time (and keep their jobs?)

Input

The first line of input contains a single integer, $$$n$$$ ($$$1 \leq n \leq 100$$$), representing the number of dishes.

The second line contains $$$n$$$ uppercase letters, $$$s_1, \ldots, s_n$$$, which is the current ordering of the dishes.

The third line contains $$$n$$$ uppercase letters, $$$t_1, \ldots, t_n$$$, which is the correct ordering of the dishes.

Output

Output a single integer, the minimum number of swaps Albert needs to do to get the dishes in the right order. If it is not possible to rearrange the dishes, output -1.

Examples
Input
5
AAAAB
BAAAA
Output
4
Input
10
ABCDEFGHIJ
ABCDEFGHIK
Output
-1
Input
10
CGCCIBUCZF
ICCBCUZCFG
Output
13
Note

In the first case, Meri swaps the B with the element on its right 4 times so that it reaches the front of the line.

In the second test case, there is no dish K, so Meri cannot achieve the correct dish ordering.

F. Chef Circle
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

As the chefs await the dishes to be finalized, they sit around a circular table. Let the chefs be $$$1, 2, \dots, n$$$, where $$$n$$$ ($$$1\leq n \leq 10^5$$$) represents the number of chefs — yes, being the international chef's day, we may have many chefs join us, and we say chef $$$i$$$ has tastebud index $$$C_i$$$ ($$$1 \leq C_i \leq 10^9$$$).

As the judging process begins, a waiter stands behind chef $$$k$$$ ($$$1\leq k \leq n$$$), and pass the dish to the chef, so that the chef may taste and judge the dish. Once that is completed, the waiter moves on to chef $$$k+1$$$; if $$$k=n$$$, then the waiter would move on to chef $$$1$$$. This process (of passing the dish, recording the chef's rating, and moving to the next chef) continues until every chef has had the chance to taste the dish, and each time, the chef's tastebud index would be added up.

The chefs are impatient and that impacts their tastebuds' sensitivity: if they are the $$$i$$$th chef to be given the dish, their tastebud index is multiplied by $$$i$$$. As the contest organizer, you desire the maximum sum of tastebud index so that the judged dish is under the most rigorous scrutiny from the chefs' tastebuds: so it is your job to determine the optimal total tastebud index obtainable from the $$$n$$$ chefs given their tastebud indexes over all the possible chefs that the waiter may start with.

Input

The first line consists of one number, $$$n$$$, representing the number of chefs.

The second line consists of $$$n$$$ numbers, representing the tastebud index $$$C_1, C_2, \dots, C_n$$$ of chefs $$$1 \dots n$$$.

Output

Only one number representing the maximum sum of the total tastebud index with the impatience multiplier as described earlier.

Examples
Input
6
2 3 5 1 9 10
Output
132
Input
3
1 4 2
Output
16
Note

There are a total of 6 possible chefs that the waiter may start with, and we will calculate the total tastebud index with impatience multiplier for each possibility:

Beginning from chef 1: $$$1\times 2 + 2\times 3 + 3\times 5 +4\times 1 + 5\times 9 + 6\times 10 = 132$$$

Beginning from chef 2: $$$6\times 2 + 1\times 3 + 2\times 5 +3\times 1 + 4\times 9 + 5\times 10 = 114$$$

Beginning from chef 3: $$$5\times 2 + 6\times 3 + 1\times 5 +2\times 1 + 3\times 9 + 4\times 10 = 102$$$

Beginning from chef 4: $$$4\times 2 + 5\times 3 + 6\times 5 +1\times 1 + 2\times 9 + 3\times 10 = 102$$$

Beginning from chef 5: $$$3\times 2 + 4\times 3 + 5\times 5 +6\times 1 + 1\times 9 + 2\times 10 = 78$$$

Beginning from chef 6: $$$2\times 2 + 3\times 3 + 4\times 5 +5\times 1 + 6\times 9 + 1\times 10 = 102$$$

Of which, beginning from chef 1 yields the best total tastebud index, so we return that index, which is 132.

G. Food Quiz
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

As the chef of a highly-successive restaurant, you have so many wonderful dishes on your menu that your diners can't figure out what to order! To help them, you created a multiple-choice quiz that has $$$n$$$ questions, each with $$$m$$$ answer choices. The $$$i$$$th answer choice for each question choice has value $$$v_i$$$. There are also $$$q$$$ different types of food.

When taking a quiz, a diner chooses exactly one choice per question. They then add up the corresponding values for each question and get some final score $$$S$$$. The $$$k$$$th food has some associated interval $$$[l_k, r_k]$$$, and each pair of intervals is disjoint. If $$$l_k \leq S \leq r_k$$$, then the quiz determines that the diner should order $$$k$$$th food.

After making the quiz, you want to make sure it is actually possible to get any of the foods as the result of the quiz. For each of the $$$q$$$ foods, can you help figure out if it is possible to pick some combination of answer choices and get a score that is within the interval for that food?

Input

The first line contains integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 20$$$) – the number of questions in the quiz and the number of answer choices per question.

The second line contains $$$m$$$ integers $$$v_1, v_2, \dots, v_m$$$ ($$$1 \leq v_i \leq 20$$$) – the values for each of the answer choices.

The third line contains the integer $$$q$$$ ($$$1 \leq q \leq 20$$$) – the number of possible food choices.

The following $$$q$$$ lines contain integers $$$l_i, r_i$$$ ($$$0 \leq l_i \leq r_i \leq 20n$$$) – the interval $$$[l_i, r_i]$$$ in which the score must lie to pick food $$$i$$$. You are guaranteed that for $$$i \neq j$$$, then $$$[l_i, r_i]$$$ and $$$[l_j, r_j]$$$ do not intersect, i.e. the intervals are pairwise disjoint.

Output

For each food, output "YES" (without quotes) if it is possible to pick that food, and "NO" otherwise.

You can output "YES" and "NO" in any case (for example, strings "yES", "yes" and "Yes" will be recognized as a positive response).

Examples
Input
1 3
1 3 5
6
1 1
2 2
3 3
4 4
5 5
6 20
Output
Yes
No
Yes
No
Yes
No
Input
2 4
2 3 4 5
3
12 20
1 3
6 11
Output
No
No
Yes

H. Cooking Timer
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Timmy really likes observing the $$$N$$$ analog cooking clocks on the wall. Each of the $$$N$$$ analog clocks has three hands: hours $$$h(0\leq h \lt 24)$$$, minutes $$$m(0\leq m \lt 60)$$$, and seconds $$$s(0\leq s \lt 60)$$$. For each of the $$$N$$$ clocks, Timmy will say what the minimum angular difference between any two hands is, in degrees. Your job is to predict what Timmy will say.

Input

The first line will contain $$$N (1\leq N\leq 10^5)$$$, the number of analog clocks. Each of the following $$$N$$$ lines will contain three integers: $$$h, m, s$$$, the current hour, minute, and second, respectively, shown on the clock.

Output

On every new line, print the degrees of the minimum angular difference between any two hands. Your answer will be treated as correct up to a difference of $$$10^{-6}$$$.

Example
Input
5
12 0 0
1 2 3
2 3 4
3 4 5
4 5 6
Output
0
5.7
5.6
5.5
5.4

I. McDaniel's
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

McDaniel's is a world–renowned restaurant run by Michelin Star Chef Ronald McDaniel.

Today is International Chef's Day, and Chef Ronald will be exclusively serving 1 item, the Ronald Burger. Chef Ronald intends to serve $$$N$$$ burgers with the $$$i^{th}$$$ burger having flavor value $$$f_i$$$.

You have recently been hired as a SWE intern at McDaniel's, and there is really no useful work for you to do, so Ronald gives you the following task:

For every burger $$$i$$$, count the number of burgers $$$j$$$ where:

1. $$$j \lt i$$$ and $$$f_j \lt f_i$$$

2. No burger $$$k$$$ exists where $$$j \lt k \lt i$$$ and $$$f_j \lt f_k$$$.

Input

The first line contains a single integer $$$N (1 \leq N \leq 10^5)$$$, the number of burgers Ronald will make.

The next line contains $$$N$$$ integers where the $$$i^{th}$$$ integer describes $$$f_i (1 \leq f_i \leq 10^9)$$$, the flavor value of the $$$i^{th}$$$ burger.

Output

Please output $$$N$$$ lines with the $$$i^{th}$$$ line containing a single integer: the count for the $$$i^{th}$$$ burger.

Examples
Input
5
1 3 5 2 4
Output
0
1
1
0
1
Input
10
1 2 3 4 5 6 7 8 9 10
Output
0
1
1
1
1
1
1
1
1
1
Input
8
7 9 1 5 2 3 6 4
Output
0
1
0
1
0
1
2
0
Input
8
7 6 5 4 3 2 1 8
Output
0
0
0
0
0
0
0
7
Input
2
1 1000000000
Output
0
1

J. Smoky Salmon
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Chef Maxine is in a busy $$$N$$$ by $$$M$$$ kitchen trying to cook up some salmon for the night's dinner rush. Due to the busy night, the kitchen has become filled with smoke. Maxine has to keep running back and forth to the refrigerator to get more fresh salmon and is getting exhausted. She must navigate around various obstacles in the kitchen to get to the fridge and grab more salmon in the way that will leave her least exhausted.

While normally walking through a tile adds $$$1$$$ to her exhaustion, walking through the smoke makes it harder to breathe, so it adds to her exhaustion by $$$3$$$. Specifically, she gets more exhausted if there is smoke on the tile as she is leaving it. The smoke appears to take on a repeating pattern of size $$$N$$$ by $$$K$$$ and drifts left by one every time step. This means at the start the first column of smoke is over the first column of the map, continuing to the right and cutting off/repeating as necessary to cover the map. At the second time step, the second column of smoke is over the first column of the map, still continuing and cutting off/repeating as necessary. This continues, with a new column of smoke appearing above the rightmost column of the map at each timestep.

At each timestep, Chef Maxine must either walk up, down, left, right, as long as there are no obstacles at this square. She always avoids staying still so it doesn't look like she's wasting time. Chef Maxine wants to know what the least exhausted she could possibly be by the time she reaches the fridge.

Input

The first line will consist of $$$3$$$ integers $$$N, M, K$$$ $$$(1 \leq N, M, K \leq 100)$$$ where $$$N$$$ is the number of rows in both the kitchen and the smoke pattern.

The following $$$N$$$ rows will each consist of $$$M$$$ characters defining the layout of the kitchen. A '#' represents an obstacle, '.' represents free space, 'C' indicates the starting position of the chef, and 'R' represents the location of the refrigerator.

The following $$$N$$$ rows will each consist of $$$K$$$ characters defining the repeating pattern of the smoke. A '1' indicates there is smoke in this location and a '0' indicates there is not.

Note: It is guaranteed there exists at least some path from 'C' to 'R' in the kitchen.

Output

Your output should consist of a single integer indicating the least exhausted Chef Maxine could be by the time she reaches the fridge.

Examples
Input
3 3 4
C.#
...
..R
0101
1010
1111
Output
4
Input
3 3 2
C.#
...
#.R
01
01
01
Output
6
Input
1 3 4
C.R
1001
Output
4
Note

Sample 1:

We start at C. We move over to the right which adds 1 to our exhaustion since there was no smoke on C. We then move down which adds 1 to our exhaustion. We move right again and then finally move down. None of these moves caused us to leave a square with smoke in it, so we get a total exhaustion of 4.

Sample 2:

We start at the C. We move over to the right, adding 1 exhaustion. There is still no smoke in the current tile, so we go down adding another 1. Now there is smoke in this tile, so when we move down again it adds 3. Finally, there is no smoke so we move right to the R which adds 1 to our exhaustion for a total of 6.

K. Donut Rings
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Emily is a famous donut chef, known worldwide for her critically acclaimed donuts of varying sizes. Being at the forefront of donut development, Emily has come up with an idea for a new donut creation: nesting donuts within other donuts! Emily currently has $$$n$$$ donuts, the $$$i$$$th of which can be described by two integers $$$r_i$$$ and $$$R_i$$$, denoting the inner and outer radius of the donut — the area between the circles of radius $$$r_i$$$ and $$$R_i$$$ being the donut itself, and the area within the circle of radius $$$r_i$$$ being the empty space making up the hole of the donut. A donut can be nested within another donut if it can fit within the hole of the other donut; in other words, if its outer radius is less than or equal to the inner radius of the other donut. Emily would like to take some of her donuts and nest them within each other to form a series of concentric donuts, which she is calling a "donut ring".

Some examples of valid and invalid donut rings:

$$$\color{green}{\text{Valid}}$$$.$$$\color{red}{\text{Invalid}}$$$. The donuts are not nested.$$$\color{red}{\text{Invalid}}$$$. The donuts are not concentric.

Obviously, critics would be pleased by a donut ring that contains a large amount of donut, but too much empty space inside the ring detracts from the presentation as well! To this end, define the beauty of a donut ring as the area of the donuts in the ring, minus the area of the empty space contained in the ring.

Emily has high expectations for her creations, so she wants to create a donut ring with the greatest beauty. Unfortunately, she has specialized too much in donut making and neglected her studies in donut math, so she has turned to you for help! Can you help Emily find the maximum beauty of a donut ring that she can make? Output this value divided by $$$\pi$$$.

Input

The first line of input contains a single integer $$$n$$$ $$$(1\leq n\leq10^5)$$$ — the number of donuts Emily has.

The $$$i$$$th of the next $$$n$$$ lines contain two integers, $$$r_i$$$ and $$$R_i$$$ $$$(1\leq r_i \lt R_i \leq 10^9)$$$, denoting the inner and outer radius of the $$$i$$$th donut.

Output

Output a single integer, the maximum beauty of a donut ring that Emily can make divided by $$$\pi$$$.

Examples
Input
3
1 2
2 3
3 4
Output
14
Input
1
75 100
Output
-1250
Input
5
9 10
6 7
3 7
1 6
15 16
Output
47
Note

In the first example, the Emily can use all three donuts to create a donut ring, with donut area $$$15\pi$$$ and enclosed empty space of $$$\pi$$$, resulting in a beauty of $$$14\pi$$$.

In the second example, Emily only has one donut, so the only donut ring she can make is comprised of just that donut with donut area $$$4375\pi$$$ and enclosed empty space of $$$5625\pi$$$, resulting in a beauty of $$$-1250\pi$$$.