UT 104c Final Exam
A. Crypto Catastrophe
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

On a whim, you "invested" $200 in cryptocurrency. After monitoring the markets for a few days, you notice that the (fiat) value of your portfolio seems to be changing according to the formula

$$$$$$v(t) = 100e^{-A t} + 100 e^{-B t}$$$$$$ where $$$t$$$ is the time in days since you bought the cryptocurrency and $$$A$$$ and $$$B$$$ are positive constants. From your calculus classes, you know that $$$v(t)$$$ is a strictly decreasing function.

You don't want to lose all of your money, so you've decided to sell when the value of your portfolio becomes half of its starting value: in other words, when $$$v(t) = 100.$$$

Assuming that the value of your portfolio continues to follow the formula above, at what time (value of $$$t$$$) should you sell the cryptocurrency?

Input

The only line of input consists of two space-separated real numbers $$$A$$$ and $$$B$$$. These constants satisfy $$$0.5 \leq A, B \leq 50$$$.

Output

Print the value of $$$t$$$ for which $$$v(t) = 100$$$. Your answer will be judged correct if it matches the judge solution with absolute or relative error $$$10^{-4}$$$.

Hint: this means you need to print your answer with many digits of precision.

Examples
Input
0.67 42.0
Output
0.0725691653788089752197265625
Input
3.14159265 2.71828
Output
0.2370033897459506988525390625
Note

All popular languages have built-in support for calculating $$$e^x$$$.


Java:

double result = Math.exp(x);


Python:

import math

result = math.exp(x)


C++:

#include <cmath>

double result = std::exp(x);

B. Theme Park Tickets
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You recently got hired by a company in Orlando, and you've decided to take advantage of all of the theme parks there. You and your friends have coordinated and decided on the days in the coming year that you wish to visit the theme park.

Now, you need to buy tickets. The theme park offers several types of ticket: each ticket type has a certain price and grants you admission to the park for a certain number of consecutive days. (You don't have to attend the park on all of those days if you don't want to; but you won't get a refund for unused days!). You can buy multiples of each ticket type and you may assume that all ticket types are available starting on all days of the year (no day is sold out).

What is the cheapest total cost you need to pay for admission to the park on your chosen days?

Input

The first line of input contains two space-separated integers $$$D$$$ and $$$T$$$: the number of days you wish to visit the park $$$(1 \leq D \leq 365)$$$ and the number of ticket types available $$$(1 \leq T \leq 10).$$$ The next line contains $$$D$$$ strictly increasing space-separated integers $$$d_i$$$ $$$(1 \leq d_i \leq 365)$$$: the days of the year that you want to visit the theme park. Each of the final $$$T$$$ lines describe a ticket type. Each line has contains two space-separated integers $$$k$$$ and $$$p$$$: the number of consecutive days that you can enter the park using a ticket of this type $$$(1 \leq k \leq 365)$$$; and the cost of the ticket in dollars $$$(1 \leq p \leq 10\,000)$$$.

Output

Print an integer: the fewest dollars you need to spend for admission to the park on all of your chosen days, assuming you buy tickets optimally.

Examples
Input
6 2
2 4 7 9 364 365
1 100
7 199
Output
498
Input
6 3
1 2 3 4 5 6
3 100
6 250
5 150
Output
200
Note

One optimal way to buy tickets for Sample Input 1 is to buy two 7-day tickets and one 1-day ticket. The 7-day tickets covers days (2, 4, 7) and (364, 365), and the 1-day ticket covers day 9.

C. Dirichlet's Theorem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A famous theorem in number theory says: for any two positive integers $$$a, b$$$ with no common factors, there are infinitely many primes $$$p$$$ of the form $$$p = ax + b$$$ (for $$$x$$$ an integer).

For example, here are some primes of the form $$$4x + 1$$$: $$$5, 13, 17, 29, 37, \ldots$$$.

Here are some primes of the form $$$4x + 3$$$: $$$3, 7, 11, 19, 23, 31, \ldots$$$.

There is only one prime of the form $$$4x + 2$$$, but that is not a counterexample since $$$4$$$ and $$$2$$$ have a common factor.

You would like to check the plausibility of the above theorem computationally. Given $$$a$$$ and $$$b$$$, how many of the primes less than ten million are of the form $$$ax + b$$$?

Input

The only line of input contains two space-separated integers $$$a$$$ and $$$b$$$. They satisfy the bounds $$$1 \leq b \lt a \leq 10^4$$$. It is guaranteed that $$$a$$$ and $$$b$$$ are relatively prime (share no common factors).

Output

Print the number of primes less than ten million of the form $$$ax + b$$$ (for $$$x$$$ an integer).

Examples
Input
4 1
Output
332180
Input
4 3
Output
332398
Input
10000 9999
Output
168

D. Boggling Word
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In Boggle, you are given a grid of letters, and need to form words using letters from the grid.

To form a word, you start at any square, then trace a path through the grid by moving from your current square to any adjacent square (in the four orthogonal or four diagonal directions). Each square you visit adds a letter to the word. You cannot visit the same square more than once.

For example, given the following grid: 


ABCD
HGFE
IJOL
PONM

it is possible to form MOON, FLED, and HAG. HIGH is not a valid word you can form using the grid, because it requires visiting the same square (the H) more than once.

Given a grid and a target word, is it possible to form the target word according to the above rules?

Input

The first four lines of input contain exactly four characters each, and specify the letter grid. The fifth line of input contains the target word, which will have length at least $$$3$$$ letters and at most $$$10$$$ letters.

"Letters" in this problem are uppercase ASCII characters A through Z.

Output

Print POSSIBLE if it is possible to form the target word using the Boggle rules described above. Print IMPOSSIBLE otherwise.

Examples
Input
ABCD
HGFE
IJOL
PONM
FLED
Output
POSSIBLE
Input
ABCD
HGFE
IJOL
PONM
HIGH
Output
IMPOSSIBLE
Input
ZZZZ
ZZZZ
ZZZZ
ZZZZ
ZZZZZZZZZZ
Output
POSSIBLE
Note

Duplicate letters in the grid are allowed (like the O in Sample Input 1.)

E. Snowfall Statistics
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Winter is coming. To help the state prepare for the annual freak Austin winter storm, you've volunteered to build an app that visualizes historical temperature statistics.

The state has numbered its counties from $$$1$$$ to $$$C$$$, in a way that nearby counties geographically have nearby numbers. The state has also provided you with the record low temperature recorded for each county.

Users will interact with your app in two ways.

1. They can ask your app to report the lowest recorded temperature across all counties in the range $$$[L, R]$$$ inclusive. In other words, if $$$T_i$$$ is the lowest temperature recorded for county $$$i$$$, this query asks for $$$$$$\min\left(T_L, T_{L+1}, \ldots, T_{R-1}, T_R\right).$$$$$$

2. Users can report a temperature for a county. If this temperature is lower than the lowest historical temperature in that county, you should take the new value into account for all subsequent queries.

Implement the backend for an app with this functionality.

Input

The first line of input contains two space-separated integers $$$C$$$ $$$(1 \leq C \leq 50\,000)$$$ and $$$Q$$$ $$$(1 \leq Q \leq 100\,000)$$$: the number of counties in the state, and the number of times the user interacts with the app.

The next line contains $$$C$$$ space-separated integers $$$T_i$$$ $$$(-50 \leq T_i \leq 120)$$$: the record low temperature of each county in the state.

The final $$$Q$$$ lines record the user interactions with your app, in order. Each interaction has one of the following two forms:

  • QUERY $$$L$$$ $$$R$$$: asks for the lowest temperature ever recorded across countries $$$L$$$ through $$$R$$$, inclusive. $$$L$$$ and $$$R$$$ satisfy the bounds $$$1 \leq L \leq R \leq C$$$. Print this lowest temperature.
  • OBSERVED $$$i$$$ $$$T$$$: reports an observation of temperature $$$T$$$ in county $$$i$$$ $$$(1 \leq i \leq C; -50 \leq T \leq 120)$$$. Do not print anything, but take this observation into account when computing lowest recorded temperature in later queries.

It is guaranteed that at least one of the $$$Q$$$ interactions is of type QUERY.

Output

For each interaction of type QUERY, print the requested lowest recorded temperature across those counties (see above). Print one query result per line.

Example
Input
5 6
5 -10 15 0 -2
QUERY 1 5
OBSERVED 2 15
QUERY 1 3
OBSERVED 4 -19
OBSERVED 5 -3
QUERY 1 5
Output
-10
-10
-19