Cấp số cộng

Cho dãy \(a_{1}, a_{2}, \ldots, a_{n}\) gồm các số tự nhiên. Cần thực hiện \(q\) truy vấn, mỗi truy vấn là một trong hai thao tác sau:

1. Nhập vào hai số nguyên \(i, u\) \((1 \leq i \leq n, 0 \leq u \leq 10^{9})\). Cập nhật \(a_{i} = u\).
2. Nhập vào hai số nguyên \(p, k\) \((1 \leq p, k \leq n)\). Hãy tính tổng \(a_{p} + a_{p + k} + a_{p + 2k} + \ldots + a_{p + uk}\) với u là số nguyên lớn nhất sao cho \(p + uk \leq n\).

Input

• Dòng đầu tiên chứa một số nguyên dương \(n\) \((n \leq 2 \times 10^{5})\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) \((0 \leq a_{i} \leq 10^{9})\).
• Dòng thứ ba chứa một số nguyên dương \(q\) \((q \leq 2 \times 10^{5})\), số lượng truy vấn.
• \(q\) dòng tiếp theo, mỗi dòng có một trong hai dạng sau:
  • \(1\) \(i\) \(u\): cập nhật \(a_{i} = u\).
  • \(2\) \(p\) \(k\): in ra tổng \(a_{p} + a_{p + k} + a_{p + 2k} + \ldots\).

Output

• Với mỗi truy vấn 2, in ra đáp số trên một dòng.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n, q \leq 2000\).
• Subtask \(2\) (\(40\%\) số điểm): đều là loại 2 (không có truy vấn cập nhật).
• Subtask \(3\) (\(40\%\) số điểm): không có rằng buộc gì thêm.

Example

8
6 7 1 3 9 0 7 5
5
2 1 1
2 3 2
1 5 3
2 1 1
2 3 2

38
17
32
11

Cho dãy số \(1, 3, 6, 10,\ldots\)

Hãy tìm số hạng thứ \(n\) với \(n\) được nhập từ bàn phím.

Input

• Một số nguyên dương \(n\) \((0 < n \leq 10^9)\)

Output

• Một số là số hạng thứ \(n\) của dãy số

Example

4

10

Nếu các bạn có người yêu như Ami, hẳn các bạn không bỏ qua bất cứ dịp gì để rủ người yêu đi chơi, hẹn hò, làm những điều mà ai cũng muồn, vân vân mây mây. Ami cũng thế.

Ngày sinh nhật của LN là một dịp cực kì thuận lợi với Ami. Cậu đã muốn làm LN vui ở những ngày bình thường. Và ở ngày sinh nhật, cậu còn muốn làm LN vui gấp trăm lần. Tối hôm đó, vào lúc 6 giờ 9 phút, Ami đèo LN trên chiếc xe đạp. Một cảnh tượng thật ngọt ngào. Vì sao lại là xe đạp ? Vì LN là cô gái đơn giản, xuất thân từ vùng quê trù phú, thanh bình. Vì xe đạp là minh chứng cho một tình yêu không vật chất. Vì xe đạp làm thời gian như chậm dần. Và cũng vì xe đạp làm con người gần gũi và thấu hiểu nhau hơn.

                              “Cậu và tớ trên một chiếc xe đạp con.

                               Mình cùng đánh dấu một tình yêu vàng son.

                               Một tình yêu không trở ngại, không vật chất.

                               Tình yêu làm đẹp đẽ cả những điều tí hon” – Credit Vi Cây Đi.

Tóm lại, các bạn được cho một dãy số, hãy xác định xem dãy số đó có phải cấp số cộng không. Một dãy \(a_1,a_2,a_3,…a_n\) là một cấp số cộng khi với mọi \(1 \le i < n\), \(a_{i+1} – a_{­i}\) là không đổi (hằng số).

Input

• Dòng đầu một số nguyên dương \(N (1 < N \le 10^3)\).

• Dòng tiếp theo gồm \(N\) số nguyên dương \(a_i (a_i \le 10^9)\).

Output

• Nếu dãy số là một cấp số cộng , các bạn hãy in ra \(k = a_{i+1} – a_i\).

• Nếu dãy số không là một cấp số cộng, các bạn hãy in NO.

Example

5
1 3 5 7 9

2

5
1 2 5 6 7

NO

Cho \(3\) số \(a, b, c\). Ba số đó tạo thành một cấp số cộng hoặc nhân. Hãy tìm số tiếp theo của dãy số đó.

Input

• Nhập vào ba số \(a, b, c\) (\(-10^{5} \le a, b, c \le 10^{5}\)).

Output

• In ra đáp án.

Example

2 4 6

8

2 4 8

16

Cho ba số nguyên \(a, b, c\). Hãy cho biết \(a, b, c\) lần lượt tạo thành một cấp số cộng hay là một cấp số nhân.

Input

• Gồm một dòng chứa ba số nguyên \(a, b, c\) \((1 \le a \le b \le c \le 1000)\)

Output

• In ra một dòng 'cap so cong' nếu ba số tạo thành một cấp số cộng, hoặc 'cap so nhan' trong trường hợp còn lại.

Example

2 4 6

cap so cong

2 4 8

cap so nhan

Cho ba số nguyên \(a, d\) và \(n\).

• \(a\) là số hạng đầu tiên của một cấp số cộng.
• \(d\) là công sai (hiệu giữa hai số hạng liên tiếp).
• \(n\) là số lượng số hạng.

Hãy tính tổng của \(n\) số hạng đầu tiên của cấp số cộng đó.

Input

• Một dòng duy nhất chứa ba số nguyên \(a, d, n\) (\(|a|, |d| \le 10^6, 1 \le n \le 10^{12}\)).

Output

• Một số nguyên duy nhất là tổng của \(n\) số hạng đầu tiên của cấp số cộng.

Example

1 2 3

9

2 3 4

26