Description

Recently your team noticed that the computer you use to practice for programming contests is not good enough anymore. Therefore, you decide to buy a new computer.

To make the ideal computer for your needs, you decide to buy separate components and assemble the computer yourself. You need to buy exactly one of each type of component.

The problem is which components to buy. As you all know, the quality of a computer is equal to the quality of its weakest component. Therefore, you want to maximize the quality of the component with the lowest quality, while not exceeding your budget.

Input

On the first line one positive number: the number of testcases, at most 100. After that per testcase:

• One line with two integers: 1 ≤ n ≤ 1000, the number of available components and 1 ≤ b ≤ 1000000000, your budget.
• n lines in the following format: ``type name price quality'', where type is a string with the type of the component, name is a string with the unique name of the component, price is an integer (0 ≤ price < 1000000) which represents the price of the component and quality is an integer (0 ≤ quality ≤ 1000000000) which represents the quality of the component (higher is better). The strings contain only letters, digits and underscores and have a maximal length of 20 characters.

It will always possible to construct a computer with your budget.

Output

Per testcase:

• One line with one integer: the maximal possible quality.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The Prime Minister and his Accumulated Council of Ministers(ACM) are trying hard to find all possible terrorist locations. In his dream, the Prime Minister gets a message from God suggesting that the answer to all terrorist problems are numbers(say one such number is X) such that the number of factors of X(including 1 and X) is prime. These numbers supposedly contain the encrypted locations of terrorists. Since the ACM has no programmer, the Prime Minister needs your help in finding out such numbers.

Note:- 1 is not considered a prime number .

Input

The first line of input will contain an integer T ≤ 20 denoting the number of test cases. T lines follow, one per test case.

Each test case will be a line formatted as "L H" where L and H are integers and 0 ≤ H ≤ 10000

Output

Output one line per case a space separated list of all integers(sorted ascending) lying between L and H(both inclusive) such that the number of factors of each integer is prime.In case no such integer exist output -1.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Creating a good and easy Graphical user interface is the heart of operating a computer in modern days. One important part of this interface is enabling users to give inputs using mouse and keyboard. Many different types of forms are there to take inputs from users. Such as (a) Text Box (b) Radio Button (c) Check Box (d) Combo Box etc. In this problem we will concentrate on check box.

Check boxes are used when a user needs to select more than one choice. Such a checkbox is shown in the figure on the left below. The problem with checkbox is that when someone has to choose n options or names he has to make n clicks, which can be very annoying when n is high. So the new software giant toggle is using a new type of checkbox, which shows good performance when number of boxes to be checked is high. In normal check box, a box is checked or unchecked if and only if it is clicked but in toggle checkbox when a box is clicked then all the boxes below it is also gets its status. That is if a box is originally not checked then if someone clicks this box then this box and all the boxes below it will be checked. Similarly if a box is checked and someone clicks on it then it will become unchecked and so will all the boxes below it. So the selection made on the left can be made by only five clicks (The boxes that has to be clicked are marked with red or dark square on the right figure) in toggle checkbox (We are calling naming new type of checkbox as “toggle checkbox”).

Figure 1: 12 clicks are required in ordinary checkbox	Figure 2: 5 clicks are required in toggle checkbox.

The researchers of toggle have shown that toggle checkboxes show better performance when at least 50% boxes are to be checked. For example for the selection shown in the above picture we needed 12 clicks to check 12 boxes in normal checkbox but only five clicks were required for toggle checkboxes. So in this situation toggle boxes show better performance. In many other selection, toggle checkbox would also show strictly better performance. Your job is to count in how many selection patterns (where at least m boxes out of the n boxes in the checkbox are to be selected) toggle check box would show better performance and in how many selection patterns ordinary checkbox would show better performance.

Input

The input file contains 1000 lines of inputs. The description of each line is given below:

Each line contains two integers n (0 < 64) and m (0 ≤ m ≤ n). These two values indicate that you have to consider a checkbox with n boxes to check and consider only the input patterns where at least m of them are checked. Assume that initially all the boxes are unchecked.

Input is terminated by a line containing two zeroes. This line should be processed.

Output

For each line of input produce one line of output.

This line contains the serial of output followed by two integers TC and NC. Here TC is the total number of selection patterns where toggle checkbox requires less clicks and NC is the total number of selection patterns where ordinary or normal checkboxes require less clicks.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A post master wishes to automate the sorting operation at his post office, since he finds that on an average the number of people assigned to the sorting operation are either heavily loaded or idle, ultimately resulting in loss of man hours that could have been efficiently used. He comes up with an idea of an automatic sorting machine that has a fixed capacity to hold the input letters and that sorts the letters at a fixed output rate. Depending upon the arrival of letters to the sorter, once the sorter is full of letters, the excess letters that would cause the sorting box to overflow have to be dropped into a bin to be manually sorted afterwards.

You are working for a company that has been called by the postmaster for a meeting to demonstrate a software simulation of the sorter. The following scenarios need to be shown in the simulation to him:

• a) Sorter box is completely filled.
• b) Sorter box is drained out.
• c) Sorter box overflows.

At the beginning of every second:

• A certain number of messages arrive, and they are added to the sorter bin of a fixed capacity C. Excess messages cause overflow into the manual sorter bin.
• From the letters that are pending to be sorted, the sorter acts and sorts R letters.

Input

Input consists of multiple testcases.

The first line of each testcase contains three integers: C R M (1 ≤ M ≤ 100; 1 ≤ R ≤ C ≤ 20,000) representing the capacity of the sorter, the fixed-rate of sorting of the sorter and the number of messages.

The following M lines contain one integer each, i-th line representing the number of letters that arrived, at time i. Each of these integers will be in the inclusive range [0,1000].

Input ends with a line containing three zeros.

Output

Output to each test case must begin with a line containing "Case #:". Each test-case must contain M lines, with exactly 5 integers each, which the state of the sorter after every unit of time. The five integers represent the following:

Current time (The i-th line will be just i).

Letters received (Same as the input for the i-th line).

Letters sorted (Number of letters the sorter sorted at this unit of time; must be less than or equal to R).

Sorter balance (Number of pending letters in the sorter; must be less than or equal to C).

Number of letters dumped into the manual sorter bin.

There should be a blank line after each test-case.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In the picture below you can see a triangle ABC. Point D, E and F divides the sides BC, CA and AB into m₁:m₂, m₃:m₄ and m₅:m₆ ratios respectively. A, D; B, E and C, F are connected. AD and BE intersects at P, BE and CF intersects at Q and CF and AD intersects at R.

So now a new triangle PQR is formed. Given triangle ABC it is very easy to find triangle PQR, but given triangle PQR it is not straight forward to find ABC. Your task is now to do that.

Input

First line of the input file contains an integer N (0 < N < 25001) which denotes how many sets of inputs are there. Input for each set contains six floating-point number P_x, P_y, Q_x, Q_y, R_x, R_y. (0 ≤ P_x, P_y, Q_x, Q_y, R_x, R_y ≤ 10000) in one line and six positive integers m₁, m₂, m₃, m₄, m₅, m₆ (m₁ < m₂, m₃ < m₄ and m₅ < m₆) in another line. These six numbers denote that the coordinate of points P, Q and R are (P_x, P_y), (Q_x, Q_y) and (R_x,R_y) respectively. P, Q and R will never be collinear and will be distinct and there will always be a triangle ABC for the given input triangle PQR. Also note that P, Q and R will be given in counter clockwise order in the input.

Output

For each line of input produce one line of output. This line contains six floating-point numbers. These six integers denote the coordinates of A, B and C. That is the first two integers denote the coordinate of A, the third and fourth integers denote the coordinate of B and fifth and sixth integers denotes the coordinate of C. A, B and C will appear counter clockwise order. All the output numbers should have eight digits after the decimal point.

Sample Input  Download

Sample Output  Download

Tags

Discuss