Sucrose has been entrusted with a row of ~N~ mysterious potions retrieved from Fatui hideouts, where the ~i~th potion has a magic value of ~A_i~. She will perform ~Q~ operations, each of type ~t_i~, which can be one of the following:

1. She adds a special solution to the potion at position ~q_i~, increasing its magic value by ~v_i~. Note that ~v_i~ can be nonpositive.

2. She uses her Anemo powers to multiply the magic values of all potions by a factor of ~m_i~. Note that ~m_i~ can also be nonpositive.

3. She asks you for the current magic value of the potion at position ~q_i~.

All magic values should be returned modulo ~10^9~, as it can be mathemagically proven to have the same effect.

Constraints

~1 \le N \le 2 \times 10^5~

~1 \le Q \le 5 \times 10^5~

~1 \le A_i \le 10^9~

~t_i \in \{1, 2, 3\}~

~1 \le q_i \le N~

~-10^9 \le v_i \le 10^9~

~-5 \le m_i \le 5~

Subtask 1 [5%]

~1 \le N, Q \le 100~

Subtask 2 [35%]

There are no type ~1~ operations. Formally, ~t_i \neq 1~.

Subtask 3 [60%]

No additional constraints.

Input Specification

The first line of input contains ~2~ space separated integers, ~N~ and ~Q~, the number of potions and the number of operations.

The second line of input contains ~N~ space separated integers, ~A_i~, the initial magic value of each potion.

The next ~Q~ lines of input contains ~(t_i, q_i, v_i)~ for type ~1~ operations, ~(t_i, m_i)~ for type ~2~ operations, and ~(t_i, q_i)~ for type ~3~ operations.

Output Specification

For each type ~3~ operation, output ~1~ integer on its own line, the magic value of the queried potion, modulo ~10^9~.

Sample Input 1

5 3
1 2 3 4 2
1 3 5
2 4
3 3

Sample Output 1

32

Explanation for Sample Output 1

The first operation increases the 3rd potion's magic value by ~5~.

The second operation multiplies all potions' magic values by ~4~.

The potions' magic values after these operations are: ~[4, 8, 32, 16, 8]~.

The third operation outputs the 3rd potion's magic value, ~32~.

Sample Input 2

4 4
1 1 1 1
2 -3
3 1
2 0
3 2

Sample Output 2

999999997
0

Explanation for Sample Output 2

The first operation multiplies all potions' magic values by ~-3~.

Note that ~-3~ mod ~10^9 = 999999997~.