UTPC Contest 02-09-24 Div. 1 (Advanced)
C. Running out of Pizza Taco
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Math Club and UTPC have decided to host a collab event in which there will be pizza and tacos! Historically the ratio has been 1 pizza = 2 tacos, but due to the excellent budgeting of the Math Club financier they are now equally valued at 1:1.

As a result, people are allowed to take up to 2 items each (with items being either a pizza slice or a taco), and an extra item of their choice if they take exactly 2 sauces. Shelly is in line and has already decided her order: one taco and one slice of pizza. She counts $$$n$$$ people in front of her, and would like to know if the pizza or taco supply will possibly run out before she gets there. Given that there are $$$X$$$ slices of pizza and $$$Y$$$ tacos and $$$Z$$$ sauces, please help Shelly figure out if there is a possibility of running out of either item before her turn.

Input

The first line contains one nonnegative integer $$$n\ (0 \leq n \leq 10^5)$$$, the number of people before Shelly. The second line contains three positive integers $$$X$$$, $$$Y$$$, and $$$Z\ (0 \lt X,Y,Z \leq 10^5)$$$, the number of pizza slices, tacos, and sauces respectively.

Output

Please print "yes" if there is a possibility of running out of pizza or taco and "no" if there is not (no quotes in the actual answer and case insensitive).

Examples
Input
21
60 70 108
Output
yes
Input
19
60 70 108
Output
no
Note

For the first case, if all 21 people choose to order pizza, there will be 18 slices left over. However, if each of the 21 people additionally take 2 sauces (which is possible since there are 108 sauces) and order pizza, there will be 0 slices of pizza left over by the time that Shelly arrives to make her order.

D. Feeding the Kids
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Mr. Reynolds is hosting a pizza party for his algorithms class after the whole class managed to score above 50 percent. There are $$$N$$$ $$$(1 \leq N \leq 10^5)$$$ students in his class, and each of them wants a certain number of slices of pizza. Unfortunately, Mr. Reynolds has a limited budget and has already purchased $$$K$$$ $$$(1 \leq K \leq 10^5)$$$ pizzas, but he has not cut them up into slices yet.

The process of receiving pizza is as follows: the students will line up in a single file line, and each student will demand $$$d_i$$$ slices of pizza ($$$1 \leq i \leq N, 1 \leq d_i \leq 10^6$$$) in that order. Then, if the current pizza has at least $$$d_i$$$ slices of pizza left, Mr. Reynolds will give the student that amount. Otherwise, Mr. Reynolds will eat the remainder of the pizza himself and open up a fresh new pizza for the student.

Mr. Reynolds is clairvoyant and happens to know the values of $$$d_i$$$, and the order in which the students will line up. Please help Mr. Reynolds figure out the minimum number of slices each pizza needs to have so that all children get their desired amount of pizza. Note that all pizzas must have the same number of slices, and it is okay if pizza is left over.

Input

The first line of the input contains two space-separated integers, $$$N$$$ and $$$K$$$.

The second line of the input contains $$$N$$$ space-separated integers, denoting $$$d_i$$$ $$$(1 \leq i \leq N)$$$.

Output

Please output the minimum number of slices each pizza needs to have so that all children get their desired amount of pizza.

Example
Input
5 3
2 10 3 6 7
Output
12

E. Pizza Expiry
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given $$$N\ (1\leq N\leq 10^5)$$$ pizzas. The $$$i$$$-th pizza consists of $$$s_i\ (2\leq s_i\leq 10^3)$$$ slices, each with side strength $$$q_i\ (1\leq q_i\leq 10^3)$$$ and crust strength $$$c_i (1\leq c_i \leq 10^3)$$$. For example, the below pizza consists of $$$4$$$ slices. Let $$$d_i$$$ be the minimum sum of strengths of slices and crusts that can hold the $$$i$$$-th pizza together, meaning that all the vertices in the picture would be in the same connected component as the other vertices, given that you draw crusts and slices to connect them. For example, the below pizza has $$$s_i = 4, q_i=2, c_i=3$$$. If we were to "connect" the crust and the slice edges this way, it is possible to connect all the vertices together with a total cost of $$$10$$$, although getting a lower $$$d_i$$$ may be possible. The center also counts as a vertex.

Being the pizza addict you are, you want to eat each pizza before it becomes soggy, otherwise, you will feel like you wasted $$$v_i\ (1\leq v_i\leq 10^9)$$$ dollars. However, you can only eat one pizza at a time. What is the minimum total possible amount of money you can feel like you wasted, given that you can eat the pizzas in any order? You start at time $$$t=0$$$, and the pizzas expire at deadline $$$d_i$$$, meaning that the $$$i$$$-th pizza cannot be eaten at $$$t\geq d_i$$$.

Input

The first line contains $$$N$$$, the number of pizzas. Then, there will be $$$N$$$ lines that follow. The $$$i$$$-th line will contain 4 integers, $$$s_i, q_i, c_i, v_i$$$.

Output

The minimum possible amount of money that you can feel like you wasted an integer on its own line.

Example
Input
4
2 1 1 4
2 2 3 4
2 3 2 2
3 2 1 10
Output
0

F. Pizza Stack
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A customer has come in with an odd request at your pizza shop. They are ordering $$$n$$$ ($$$1 \leq n \leq 1000$$$) pizzas, with each pizza having a unique radius from 1 to $$$n$$$. Additionally, they want you to stack these pizzas on top of each other (like a stack of pancakes) in a very specific way. Given a pair of pizzas $$$a$$$ and $$$b$$$ in the stack, if pizza $$$a$$$ is below pizza $$$b$$$ in the stack and pizza $$$a$$$ has a larger radius than pizza $$$b$$$, we call this a "proper" pair. The customer requests a stack of pizzas with exactly ($$$0\leq k\leq 1000$$$) proper pairs of pizzas, and you want to find out exactly how many different ways you can stack your $$$n$$$ pizzas in order to have exactly $$$k$$$ proper pairs in your stack. Note that this number can be very large, so please mod it by $$$10^9 + 7$$$.

Input

The first and only line of input consists of two integers, $$$n$$$ ($$$1 \leq n \leq 1000$$$) and $$$k$$$ ($$$0\leq k\leq 1000$$$).

Output

Print out the number of ways to create a stack of $$$n$$$ pizzas with exactly $$$k$$$ proper pairs, mod $$$10^9 + 7$$$.

Examples
Input
3 0
Output
1
Input
3 1
Output
2

G. Slicing the Pizza
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are making an infinite pepperoni pizza, which fills the entire $$$x$$$-$$$y$$$ coordinate plane. You think it might be too much to eat at once, so you decide to cut the plane in half by cutting along some line. You don't want too many pieces of pepperoni on one side, so you want the line to cut through at least $$$1/8$$$th of the pepperoni slices. You are guaranteed that at least one such line exists. Can you find it? If there are multiple lines, find any.

For this problem, assume that the pepperoni slices have radius 0, i.e. they are single points on the grid.

Input

The first line of the input contains a single integer $$$n$$$ ($$$8 \leq n \leq 10^5$$$) – the number of slices of pepperoni.

The next $$$n$$$ lines contain the coordinates of each slice of pepperoni. The $$$i$$$th line contains two integers $$$x_i, y_i$$$ ($$$1 \leq x_i, y_i \leq 10^6$$$) – the $$$x$$$ and $$$y$$$ coordinates of the $$$i$$$th slice of pepperoni, respectively.

You are guaranteed that each pair of coordinates is distinct, i.e. $$$(x_i, y_i) \neq (x_j, y_j)$$$ if $$$i \neq j$$$. You are also guaranteed there exists a valid solution.

Output

Print three space-separated real numbers $$$A, B, C$$$, which represent the line in standard form $$$Ax + By = C$$$. Please ensure $$$-10^{12} \leq A, B, C \leq 10^{12}$$$.

Let $$$D_i$$$ be $$$Ax_i + By_i$$$. A point is considered "valid" if the absolute or relative error of $$$D_i$$$ from $$$C$$$ is at most $$$10^{-6}$$$, i.e. $$$\frac{|D_i - C|}{\max(1, |C|)} \leq 10^{-6}$$$. Your answer will be considered correct if at least $$$\lfloor n / 8 \rfloor$$$ of the points are valid.

Example
Input
8
1 1
2 2
3 3
3 2
9 8
5 5
3 8
4 1
Output
-7.000000000000000 -1.000000000000000 -29.000000000000000
Note

For this sample, any line that goes through a single slice works since we only need $$$\left\lfloor \frac{8}{8} \right\rfloor = 1$$$ slices. For larger $$$n$$$, this is not the case!

H. Euclidean Pizza
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are a time traveler tasked with the duty of introducing pizza to the ancient Greeks. Along your journey, you meet the mathematician Euclid. After studying the pizza you have brought, Euclid gives you a problem. He tells you to envision the pizza as a 2D plane centered at the origin. The toppings are represented as $$$N$$$ points scattered on the plane. Additionally, the "crust" of the pizza is represented by $$$M$$$ points scattered on the plane. He defines "a slice of pizza" as a valid triangle comprised of 2 crust points and the origin. Euclid asks you to count the number of topping points that are enclosed within some valid slice of pizza (including toppings on the boundary).

Input

The first line of input contains 2 space-separated integers $$$N, M\ (0 \leq N \leq 5 \cdot 10^4, 4 \leq M \leq 5 \cdot 10^4) - $$$ the number of topping and crust points, respectively.

Note: It is guaranteed that there is at least 1 crust point in each of the 4 quadrants.

The next $$$N$$$ lines of input contain 2 space-separated integers $$$x, y\ (-10^9 \leq x, y \leq 10^9) - $$$ the $$$x$$$ and $$$y$$$ coordinates of the $$$i^{th}$$$ topping point.

The next $$$M$$$ lines of input contain 2 space-separated integers $$$x, y\ (-10^9 \leq x, y \leq 10^9) - $$$ the $$$x$$$ and $$$y$$$ coordinates of the $$$i^{th}$$$ crust point.

Note: It is guaranteed that no two points, topping or crust, have the same $$$x$$$ or $$$y$$$ values.

Output

Please output 1 integer, the total number of topping points that are enclosed within some slice of pizza.

Examples
Input
5 6
2 2
-8 0
-3 1
4 -3
0 4
8 -2
3 3
-2 6
-1 5
1 -1
-4 -4
Output
3
Input
2 5
3 -2
1000000000 1000000000
0 0
1 1
-2 2
-3 -3
4 -4
Output
0
Note

The first sample case is drawn below (toppings represented by orange points and crusts represented by black points). Two example pizza slices are also drawn. Three out of the five toppings can be enclosed by a slice. Observe that no other topping can be enclosed by a slice.

I. Pizza Tower
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Peppino Spaghetti needs to defend his pizza tower against a horde of enemies!

Each of the $$$N$$$ enemies has a distinct location $$$(x_i, y_i)$$$ as well as a strength value $$$s_i$$$. Furthermore, we define a function $$$$$$f(x, y) = \begin{cases} s_i & x = x_i \text{ and } y = y_i \text{ for some } i \in \{1, 2, \dots, N\} \\ 0 & \text{otherwise} \end{cases}.$$$$$$

In order to gauge where to set up his defenses so that his tower will stay safe, Peppino needs to calculate a function $$$$$$F(x_i, y_i) = \sum_{x \leq x_i} \sum_{y \leq y_i} f(x, y)$$$$$$ at each point $$$(x_i, y_i)$$$ for $$$i \in \{1, 2, \dots, N\}$$$. However, Peppino doesn't have much time, so he has asked you to write a computer program to speed up the calculations. Please help him out!

Input

The first line of input will contain a single integer $$$N\ (1 \leq N \leq 2 \cdot 10^5)$$$ denoting the number of enemies in the horde.

The next $$$N$$$ lines will each contain three space-separated integers $$$x_i$$$, $$$y_i$$$, and $$$s_i\ (1 \leq x_i, y_i, s_i \leq 2 \cdot 10^9)$$$ denoting the position and strength value of the $$$i^\text{th}$$$ enemy. Furthermore, it is guaranteed that $$$(x_i, y_i) \neq (x_j, y_j)$$$ for any $$$i \neq j \in \{1, 2, \dots, N\}$$$, that is, the positions of enemies are distinct.

Output

The output should consist of exactly $$$N$$$ lines, each containing a single integer. The $$$i^\text{th}$$$ line should contain the integer $$$F(x_i, y_i)$$$. Note that $$$F(x_i, y_i)$$$ could be quite large, and may not fit into a standard signed 32-bit integer.

Examples
Input
4
1 1 5
2 1 10
1 2 10
3 3 15
Output
5
15
15
40
Input
5
1 1 1
1 2 2
1 3 3
1 4 4
1 5 5
Output
1
3
6
10
15
Note

In the first sample case, $$$F(1, 1) = f(1, 1) = 5$$$, and $$$F(2, 1) = F(1, 2) = 15$$$ since $$$F(2, 1) = f(2, 1) + f(1, 1) = 10 + 5$$$ and $$$F(1, 2) = f(1, 2) + f(1, 1) = 10 + 5$$$. Also, $$$F(3, 3) = f(3, 3) + f(2, 1) + f(1, 2) + f(1, 1) = 15 + 10 + 10 + 5 = 40$$$.

In the second sample case, it can be observed that $$$F(1, y) = f(1, y) + F(1, y-1)$$$ for $$$1 \lt y \leq 5$$$.

J. Batch Please!
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In the premier episode of Hell's Kitchen – UTPC Edition, teams are competing to make meals for their hungry customers. It's the red team vs. the blue team; the red team is making pizzas, while the blue team is making burgers.

You are on the blue team, and you just made a burger – but you've botched it! The burger layers are all wrong! You've got a list of orders for burgers, and you'd like to know how you might be able to fix your burger.

Formally, let's represent a burger as a string, where each character represents a layer. For example, "pblt" might represent a burger consisting of a patty on bacon on lettuce on tomato (in that order).

You have a list of correct burgers, and you want to modify your botched burger to create these target burgers. In one operation, you may:

  1. Remove one topping from the top of your burger (for example, "pblt" $$$\rightarrow$$$ "blt")
  2. Add one topping to the top of your burger (for example, "pblt" $$$\rightarrow$$$ "epblt")
  3. Remove one topping from the bottom of your burger (for example, "pblt" $$$\rightarrow$$$ "pbl")
  4. Add one topping to the bottom of your burger (for example, "pblt" $$$\rightarrow$$$ "pbltm")
In order to figure out the easiest way to fix your burger, please determine how many operations are required to build each target burger out of the original botched burger.
Input

The first line contains a single integer $$$N\ (1 \le N \le 10^3)$$$, the number of target burgers.

The second line contains a string representing the original botched burger $$$S\ (1 \le |S| \le 10^3)$$$.

The next $$$N$$$ lines each contain a single string representing the target burgers $$$T_1,...,T_N\ (1 \le |T_i| \le 10^3)$$$.

All burgers are strings consisting only of the lowercase letters $$$a$$$ through $$$z$$$.

Output

Output $$$N$$$ lines, where line $$$i$$$ contains a single integer denoting the minimum number of operations required to build the $$$i^\text{th}$$$ target burger.

Examples
Input
3
pblt
blt
pbpb
blbl
Output
1
4
4
Input
1
pblbtllpbltt
pbpbltpbpt
Output
14
Note

In the first test case:

  1. "pblt $$$\rightarrow$$$ blt" requires a single operation.
  2. "pblt $$$\rightarrow$$$ pbl $$$\rightarrow$$$ pb $$$\rightarrow$$$ pbp $$$\rightarrow$$$ pbpb" requires four operations.
  3. "pblt $$$\rightarrow$$$ pbl $$$\rightarrow$$$ bl $$$\rightarrow$$$ blb $$$\rightarrow$$$ blbl" requires four operations.