A Squirrel Problem 2

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 64M

Problem type

ChrisT is feeling hungry. He has snacks lined up in a row, numbered from 1 to N. Each snack has C_i calories. Because ChrisT doesn't want to get too thicc, he would like to know the number of calories in snack number i. However, his house has a squirrel infestation! The squirrels like to eat the first r snacks, halving their calorie value (rounding down). Please help ChrisT!

Input Specification

The first line contains the integer N, Q\ (1 \le N, Q \le 10^5), the number of snacks, and the number of queries, respectively.

The next line will contain N space-separated integers C_i\ (1 \le C_i \le 10^8), the number of calories in each snack.

1 i, meaning that ChrisT wants to know the number of calories in snack i\ (1 \le i \le N);

2 r, meaning that the calories in the first r\ (1 \le r \le N) snacks have been halved.

Due to weak test data, additional cases have been added intended to break incorrect solutions that AC on previous test data. Data was provided by sz_8

Output Specification

For every query of form 1 i, print the number of calories in snack number i on its own line.


Subtask 1 [30%]

(1 \le N \le 10^4),\ (1 \le Q \le 10^4),\ (1 \le C_i, v \le 10^5)

Subtask 2 [70%]

No additional constraints.

Sample Input

5 7
1 2 5 3 9
1 1
2 3
1 4
2 1
1 2
2 4
1 3

Sample Output



There are no comments at the moment.