You are given a list of transactions, each of them includes transaction code, product code, selling price, and quantity. Your task is to write a program to print the average selling price for each product.

Input

• The first line contains one integer ~N~ - the number of transactions ~(1 ≤ N ≤ 10^5)~.

• Each line in the next ~N~ lines contains four integers representing a transaction. All of them are not exceed ~10^9~.

Output

• For each product, print out the product code and the average selling price. The list of products should be sorted in descending order of the average selling price and ascending order of product code.

• The average selling price should be rounded to the nearest unit in output.

Sample Input

5
1111 1 1000 2
1112 2 100 1
1113 1 500 10
1114 2 99 1
1115 3 100 2

Sample Output

1 583
3 100
2 100