to . Each snack has calories. Because doesn't want to get too thicc, he would like to know the number of calories in snack number . However, his house has a squirrel infestation! The squirrels like to eat the first snacks, halving their calorie value (rounding down). Please help !

is feeling hungry. He has snacks lined up in a row, numbered from#### Input Specification

The first line contains the integer , the number of snacks, and the number of queries, respectively.

The next line will contain space-separated integers , the number of calories in each snack.

`1 i`

, meaning that wants to know the number of calories in snack ;

`2 r`

, meaning that the calories in the first 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 **

#### Output Specification

For every query of form `1 i`

, print the number of calories in snack number on its own line.

#### Constraints

##### Subtask 1 [30%]

##### 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

```
1
3
1
1
```

## Comments