Temperature Monitoring and Query System

You are tasked with implementing a temperature monitoring system for a data center. The system records temperature readings along with their timestamps and processes a series of queries on these records. Each record is given as a pair ( (t_i, v_i) ), where ( t_i ) is the timestamp and ( v_i ) is the temperature reading.

There are three types of queries:

1. Query type 1: Given a time interval ( [l, r] ), find the maximum temperature recorded in that interval.
2. Query type 2: Given a time interval ( [l, r] ), find the minimum temperature recorded in that interval.
3. Query type 3: Given a time interval ( [l, r] ), compute the average temperature recorded in that interval and round it to the nearest integer.

All queries are guaranteed to have at least one record within the specified time interval.

Input guarantees: Timestamps in the records may not be initially sorted. You should sort them before processing the queries.

inputFormat

The input is provided via the standard input (stdin) in the following format:

(n) An integer specifying the number of temperature records.

Next (n) lines: Each line contains two integers (t_i) and (v_i) representing a timestamp and its corresponding temperature reading.

(q) An integer specifying the number of queries.

Next (q) lines: Each line contains three integers (type), (l), and (r), where (type) indicates the type of query (1 for maximum, 2 for minimum, 3 for average), and (l) and (r) specify the inclusive timestamp range for the query.

outputFormat

For each query, output the result to standard output (stdout). The results of all queries should be output in a single line separated by spaces, or each on a separate line, following the order of the queries.## sample

5
1 10
2 -5
3 20
4 15
5 -10
3
1 2 4
2 1 3
3 1 5

20 -5 6