Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3565
Stock II

Time Limit: 2 Seconds      Memory Limit: 65536 KB

The capital stock (or just stock) of a business entity represents the original capital paid into or invested in the business by its founders. It serves as a security for the creditors of a business since it cannot be withdrawn to the detriment of the creditors. Stock is distinct from the property and the assets of a business which may fluctuate in quantity and value.

Call auction is one effective way to determine the opening price. There are a lot of technical terms and rules. But in this problem, you only need to know the rules as follows:

  • There are two types of quotation: selling and buying. The actually accepted price can be higher than the selling quotation and lower than the buying quotation. For example, if SXSTAR wants to sell 000876 at 20.00 yuan, but the actually accepted price can be 21.00 yuan. In this situation, SXSTAR will be very happy.
  • The trading system sorts the quotation with two principles: price priority and time priority, basing on which, the system decides a base price that meets the following three conditions:
    1. The volume is largest;
    2. The buying quotation higher than the base price and the selling quotation lower than the base price should be wholly accepted (at the base price);
    3. If there are some quotations equal to the base price, at least one side of buyers and sellers should be wholly accepted.
  • If two or more prices meet the three conditions, the average of these base prices is the opening price. Otherwise, the base price is the opening price.

SXSTAR has bought a stock, 000876, New Hope. Its opening price increased by 10% on 5th July, 2011, but he didn't sell it out because he didn't know much about the call auction. So SXSTAR turns to you to help him to calculate the opening price and volume of one stock.

Input

There are several test cases (<=100). You should process to the end of input. For each test case, the first line has one integers N (0 <= N <= 100000). Then followed by N lines. Each line has 3 numbers. The first one is an integer, which means the quotation type, 1 is for selling and 2 is for buying. The second one is a positive real number (<= 1000000), which means the price of quotation. The third one is a non-negative integer (<= 1000000), which means the shares.

Output

For each case, you should print a single line with the opening price and volume, two numbers should be separated by a space. Your answer of opening price should round to two decimal places. If there is no opening price, print "null" instead of opening price.

Sample Input

2
1 100.05 100
2 100.05 100

Sample Output

100.05 100

Author: SHEN, Xin
Contest: ZOJ Monthly, December 2011
Submit    Status