Highest Bids

In this problem, you are given a list of products and a list of bids. Each product has a unique identifier and a base price. Each bid consists of a bidder ID, a product ID, and a bid amount. Your task is to determine the highest bid for each product. The highest bid for a product is defined as the maximum of its base price or any valid bid placed for it. If there are no bids for a product, the highest bid is its base price.

The input is provided via standard input (stdin) and the output should be written to standard output (stdout). The first line of input contains two integers: the number of products (P) and the number of bids (B). The next P lines describe the products with two integers per line: product_id and base_price. The following B lines describe the bids with three integers per line: bidder_id, product_id, and bid_amount. The output should consist of P lines, each containing the product_id and its highest bid, in the same order as the products were input.

inputFormat

The first line contains two integers P and B, representing the number of products and the number of bids, respectively. The next P lines each contain two integers: product_id and base_price. The following B lines each contain three integers: bidder_id, product_id, and bid_amount.

outputFormat

Output exactly P lines. Each line should contain two integers: the product_id and the highest bid for that product. The products must be output in the same order as they appear in the input.## sample

3 5
101 1000
102 1500
103 2000
1 101 1200
2 101 1300
3 102 1600
4 103 2200
5 102 1700

101 1300
102 1700
103 2200