Bài tập hè của Hải Ly

Cho dãy số nguyên $a_1,a_2,\dots ,a_n$. Bạn cần thực hiện $m$ truy vấn liên tiếp thuộc một trong ba loại sau:

1. 1 x v — gán $a_x=v$.
2. 2 l r — tính tổng ${\displaystyle {\sum }_{i=l}^r{f}_{i-l}·a_i\left(\mathrm{mod}{10}^9\right)}$, trong đó $f_0=f_1=1$ và $f_i=f_{i-1}+f_{i-2}$ với $i\ge 2$.
3. 3 l r d — tăng $a_x$ thêm $d$ với mọi $x$ thỏa $l\le x\le r$.

Lưu ý rằng số dư được lấy theo modulo ${10}^9$ (không phải ${10}^9+7$).

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.
• $m$ dòng tiếp theo, mỗi dòng mô tả một truy vấn theo định dạng mô tả ở trên.

Dữ liệu ra

Với mỗi truy vấn loại 2, in ra giá trị tổng cần tính theo modulo ${10}^9$ trên một dòng riêng.

Ràng buộc

• $1\le n,m\le 2·{10}^5$
• $0\le a_i\le {10}^5$
• Với truy vấn loại 1: $1\le x\le n$, $0\le v\le {10}^5$.
• Với truy vấn loại 2: $1\le l\le r\le n$.
• Với truy vấn loại 3: $1\le l\le r\le n$, $0\le d\le {10}^5$.

Ví dụ