UT 104c Midterm #1
A. Sum of Squares
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a well-known formula for the sum $$$f(n)$$$ of the first $$$n$$$ squares, $$$$$$f(n) = 1^2 + 2^2 + 3^2 + \ldots + n^2 = \frac{n(n+1)(2n+1)}{6}.$$$$$$

Write a function that computes $$$n$$$ given $$$f(n)$$$.

Input

The first line of input contains a single integer $$$T$$$, the number of test cases $$$(1 \leq T \leq 10\,000)$$$. Each of the following $$$T$$$ lines contain a single integer $$$k$$$ $$$(1 \leq k \leq 2^{60})$$$.

Output

For each test case, print a line with the positive integer $$$n$$$ satisfying $$$f(n) = k$$$. It is guaranteed that such an integer exists.

Example
Input
5
1
5
14
385
1152919708258615990
Output
1
2
3
10
1512307
Note

Hint: the largest possible value of $$$n$$$ with $$$f(n) \leq 2^{60}$$$ is $$$n=1512307$$$.

B. Winning Record
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You have been hired by the Texas Exes to build an app that helps Longhorns fans track the performance of the football team over time. One of the features they've requested is for the user to select a range of historical games; the app should then tell them whether or not the Longhorns had a winning record within that range of games.

Write an algorithm that implements this feature.

Input

The first line of input contains two integers $$$n$$$ and $$$k$$$ $$$(1 \leq n, k \leq 100\,000)$$$: the number of games in the database and the number of ranges that you need to analyze.

The next line is a string of exactly $$$n$$$ characters. Each character is either W or L, indicating that the Longhorns won or lost the game. The wins and losses are listed in chronological order from oldest game to newest.

The final $$$k$$$ lines are ranges to analyze. Each range contains two space-separated integers $$$i$$$ and $$$j$$$ $$$(1 \leq i \leq j \leq n)$$$.

Output

Print a string of $$$k$$$ characters, representing the results of your analysis for each of the $$$k$$$ ranges (in order).

For each range, print a Y if the Longhorns won more games than they lost between games $$$i$$$ and $$$j$$$ inclusive. Otherwise, print N.

(Note in particular that if the Longhorns won and lost the same number of games in a range, you should print N.)

Example
Input
11 5
WWLWLWLLLWW
1 1
1 3
6 11
2 6
1 11
Output
YYNYY

C. Buying Fruit
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You've been tasked with buying fruit to put in snack trays at your student org's annual kickoff event. You know you will need at least $$$P$$$ total pounds of fruit, so you've taken a shopping trip to HEB.

Fruit at HEB is priced in dollars per pound, and HEB only has a limited amount of each type of fruit in stock. What is the cheapest price you must pay to buy $$$P$$$ total pounds of fruit, given your options?

Although not completely realistic, for the purposes of this problem you may assume that if HEB stocks $$$k$$$ pounds of a fruit, it is possible to buy any amount of that fruit between $$$0$$$ and $$$k$$$ pounds.

Input

The first line of input contains two space-separated integers $$$P$$$ and $$$n$$$: the total pounds of fruit you need to buy $$$(1 \leq P \leq 1\,000)$$$, and the number of types of fruit sold at HEB $$$(1 \leq n \leq 100)$$$. The next $$$n$$$ lines describe the fruit on offer. Each line contains a real number $$$p$$$, the price of the fruit in dollars per pound $$$(0.01 \leq p \leq 100.00)$$$, and an integer $$$k$$$, the total pounds of that fruit that HEB has in stock $$$(1 \leq k \leq 100)$$$.

Output

If it is impossible to buy $$$P$$$ pounds of fruit given the options in stock, print -1.

Otherwise, print the cheapest price (in dollars) you must pay to purchase $$$P$$$ pounds of fruit. Your answer will be judged correct if it matches the judge solution with relative or absolute error at most $$$10^{-4}$$$.

Examples
Input
100 3
1.75 53
2.01 20
1.06 41
Output
148.27
Input
50 2
2.00 20
3.50 20
Output
-1

D. Interview Flights
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Congratulations! You've been selected by Conglomo Corp. as a finalist for a summer internship. They are flying you to their headquarters for a final in-person interview.

Some flights are more likely to arrive on time than others, and you want to maximize the probability that you arrive at the interview on time and without missing a connection. Nothing else matters: you are willing to take a longer overall trip with more flight segments if doing so has a higher chance of arriving on time than a shorter itinerary.

Given a list of flights, each of which has a starting city, ending city, and probability of arriving on time, compute the optimal itinerary for arriving at the interview without incident.

Input

The first line of input contains two space-separated integers $$$n$$$ ($$$2 \leq n \leq 50\,000$$$) and $$$m$$$ ($$$1 \leq m \leq 50\,000$$$): the number of cities the airline serves, and the number of available flights, respectively.

Each of the next $$$m$$$ lines describes one flight. A flight consists of two space-separated integers $$$s$$$ and $$$d$$$ followed by a real number $$$p$$$ ($$$1 \leq s,d \leq n$$$, $$$0.0 \leq p \leq 1.0$$$), indicating that a flight exists from city $$$s$$$ to city $$$d$$$, and that this flight arrives on time with probability $$$p$$$. All listed flights are one-way and it is guaranteed that $$$s \neq d$$$. There might be multiple flights with the same source and destination city.

City $$$1$$$ is Austin and city $$$n$$$ is Conglomo Corp. headquarters.

Output

Print the probability of arriving at your job interview on time, assuming you fly using the optimal itinerary that maximizes this probability. Your answer will be judged correct if it differs from the judge answer with relative or absolute error at most $$$10^{-4}$$$.

Assume that flight delays are independent events, so that the probability of arriving at Conglomo Corp. headquarters is the product of the probabilities that all flights along the way arrive on time.

Note that if it is impossible to travel from Austin to Conglomo Corp. headquarters, the probability of arriving on time is $$$0$$$.

Examples
Input
3 6
1 3 0.2
1 2 0.9
1 2 0.8
2 3 0.7
3 1 1.0
3 2 0.9
Output
0.630000000000000004440892098501
Input
4 5
1 2 0.5
1 3 1.0
2 3 0.9
3 2 1.0
4 1 1.0
Output
0.0