Pikachu là một cao thủ chơi bi. Pikachu có ~n~ cái quần và để chuẩn bị cho mọi lời thách đấu của mấy con gà, anh luôn nhét sẵn một số lượng bi trong quần của mình. Ban đầu không có quần nào có bi. Mỗi lần muốn chọn cái quần thứ ~i~ để mặc, anh sẽ đi từ cái quần thứ nhất đến cái quần thứ ~i~, lấy tất cả số bi trong các cái quần đó và mặc cái quần thứ ~i~ vào. Là một người ngăn nắp, sau khi giặt xong cái quần vừa mặc, anh sẽ nhét lại quần vào móc và nhét lại các viên bi như cũ. Mỗi lần thắng một trận đấu bi, anh sẽ được thêm ~x~ viên bi và anh sẽ chọn một cái quần ~p~ nào đó để nhét số bi đó vào. Vì lười tính, hãy đếm số bi mà anh ấy có khi lấy một cái quần.

Nói cho dễ hiểu, cho một mảng ~a~ có ~n~ phần tử ~(n \leq 10^5)~ đều có giá trị là ~0~. Có ~q~ truy vấn ~(q \leq 10^5)~ thuộc một trong hai loại sau:

• ~1 \; p \; x~: tăng giá trị ~a_p~ thêm ~x~ đơn vị.
• ~2 \; i~: tính tổng các phần tử ~a_1, \; a_2, \; ... , \; a_i~.

Input

• Dòng đầu chứa số ~2~ nguyên ~n, \; q~ ~(n, \; q \leq 10^5)~.
• ~q~ dòng tiếp theo chứa ~q~ truy vấn thuộc một trong hai loại trên.

Tất cả các số trong input đều dương và không quá ~10^9~.

Output

• Kết quả của các truy vấn loại ~2~ theo thứ tự.

Sample Input 1:

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

Sample Output 1:

2
12

Pikachu là một cao thủ chơi bi. Pikachu có ~n~ cái quần và để chuẩn bị cho mọi lời thách đấu của mấy con gà, anh luôn nhét sẵn một số lượng bi trong quần của mình. Ban đầu không có quần nào có bi. Mỗi lần muốn chọn cái quần thứ ~i~ để mặc, anh sẽ mặc cái quần thứ ~i~ vào và lấy hết số bi trong quần đấy. Là một người ngăn nắp, sau khi giặt xong cái quần vừa mặc, anh sẽ nhét lại quần vào móc và nhét lại các viên bi như cũ. Mỗi lần thắng một trận đấu bi, anh sẽ được thêm một số viên bi và anh sẽ nhét ~x~ viên bi vào các quần từ ~l~ đến ~r~ ~(l \leq r)~. Vì lười tính, hãy đếm số bi mà anh ấy có khi lấy một cái quần.

Nói cho dễ hiểu, cho một mảng ~a~ có ~n~ phần tử ~(n \leq 10^5)~ đều có giá trị là ~0~. Có ~q~ truy vấn ~(q \leq 10^5)~ thuộc một trong hai loại sau:

• ~1 \; l \; r \; x~: tăng giá trị ~a_l, \; a_{l + 1}, \; ... , \; a_r~ thêm ~x~ đơn vị.
• ~2 \; i~: đưa ra giá trị của phần tử ~a_i~.

Input

• Dòng đầu chứa số ~2~ nguyên ~n, \; q~ ~(n, \; q \leq 10^5)~.
• ~q~ dòng tiếp theo chứa ~q~ truy vấn thuộc một trong hai loại trên.

Tất cả các số trong input đều dương và không quá ~10^9~.

Output

• Kết quả của các truy vấn loại ~2~ theo thứ tự.

Sample Input 1:

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

Sample Output 1:

5
12
7

Cho một dãy số ~a_1, a_2, ... a_N~. Một nghịch thế là một cặp số ~u, v~ sao cho ~u < v~ và ~a_u > a_v~. Nhiệm vụ của bạn là đếm số nghịch thế.

Input

• Dòng đầu ghi số nguyên dương ~N~ ~(N \leq 10^5)~.
• Dòng sau gồm ~N~ số nguyên dương ~a_i~ ~( 1 ≤ a_i ≤ 10^5 )~.

Output

• In ra kết quả của bài toán.

Subtasks

• Subtask 1: ~n \leq 5000~. (50%)
• Subtask 2: Không giới hạn gì thêm.

Sample Input 1

3
3 1 2

Sample Output 1

2

Cho mảng ~a~ gồm ~n~ phần tử. Hãy đưa ra độ dài dãy con tăng dài nhất của mảng và số dãy con tăng có độ dài như thế lấy dư cho ~10^9 + 7~.

Input

• Dòng đầu chứa số nguyên dương ~n~ ~(n \leq 10^5)~.
• Dòng thứ hai gồm ~n~ số nguyên là các phần tử của mảng ~a~.

Tất cả các số trong input đều có giá trị tuyệt đối không quá ~10^9~.

Output

• Gồm ~2~ số nguyên là kết quả của bài toán.

Sample Input 1:

7
1 1 2 2 4 3 3

Sample Output 1:

3 12

Cho mảng ~a~ gồm ~n~ phần tử. Dãy nghịch thế độ dài ~k~ là dãy các chỉ số ~i_1, \; i_2, \; , ..., \; i_k~ sao cho ~i_1 < i_2 < ... < i_k~ và ~a_{i_1} > a_{i_2} > ... > a_{i_k}~. Hãy đưa ra số lượng dãy nghịch thế độ dài ~k~ lấy dư cho ~10^9~.

Input

• Dòng đầu chứa ~2~ số nguyên dương ~n, \; k~ ~(n \leq 10^4, \; k \leq 10)~.
• Dòng thứ hai gồm ~n~ số nguyên là các phần tử của mảng ~a~.

Tất cả các số trong input đều có giá trị tuyệt đối không quá ~10^9~.

Output

• Gồm ~1~ số nguyên là kết quả của bài toán.

Sample Input 1:

3 2
3 2 1

Sample Output 1:

3