Tribble Population Queries

You are given the initial populations of tribbles on day 1 and day 2, denoted by a and b respectively. For any day n > 2, if no update is performed, the population is normally given by the recurrence:

$$P_n = P_{n-1} + P_{n-2}$$

However, you will also receive a number of queries. There are two types of queries:

• Update query: 1 i x — update the population on day i to x.
• Query request: 2 i — output the current population on day i.

The queries are processed in the given order and updates affect future computations. Note that if a day's population was computed using the recurrence and later an update is applied to one of the preceding days, the updated value will be used for subsequent queries when recomputed.

Your task is to process all queries and for every query of type 2, output the corresponding population.

inputFormat

The first line contains two space-separated integers a and b, representing the populations on day 1 and day 2 respectively.

The second line contains an integer q, denoting the number of queries.

The following q lines each describe a query. A query can be one of the following formats:

• 1 i x — update the population on day i to x.
• 2 i — query and output the population on day i.

It is guaranteed that the queries are such that the computations will not require iterating over excessively large indices.

outputFormat

For each query of type 2, print the population on the requested day on a separate line.

## sample

3 5
5
2 5
1 3 8
2 3
1 4 13
2 4

21
8
13

</p>