Có \(n\) thùng sơn màu đỏ và \(m\) thùng sơn màu xanh xếp thành một hàng ngang. Các thùng sơn cùng màu được xếp liền nhau từ trái sang phải, hết màu này tiếp đến màu kia.

Yêu cầu: Nếu cần xếp \(k\) thùng sơn lên xe, bắt đầu từ bên trái hàng sơn, hỏi có bao nhiêu thùng sơn màu đỏ được xếp?

Input

• Dòng đầu tiên ghi số nguyên dương \(n\) \((1 \leq n \leq 100)\) và một chữ cái \(c_{1}\), ghi cách nhau dấu cách, là số thùng sơn và màu sơn của các thùng sơn được xếp bên phía trái hàng sơn. Nếu chữ cái \(c_{1}\) là R, có nghĩa là các thùng sơn màu đỏ, B là các thùng sơn màu xanh.

• Dòng thứ hai ghi số nguyên dương \(m\) \((1 \leq m \leq 100)\) và một chữ cái \(c_{2}\), ghi cách nhau dấu cách, là số thùng sơn và màu sơn của các thùng sơn được xếp bên phía phải hàng sơn. Nếu chữ cái \(c_{2}\) \((c_{2} \neq c_{1})\) là R có nghĩa là các thùng sơn màu đỏ, B có nghĩa là các thùng sơn màu xanh.

• Dòng cuối cùng ghi số nguyên dương \(k\) \((1 \leq k \leq n + m)\) là số thùng sơn màu đỏ được xếp trên lên xe.

Output

• gồm một dòng ghi số nguyên dương là số thùng sơn màu đỏ được xếp lên xe.

Example

5 R
6 B
7

5

5 B
6 R
7

2

5 R
6 B
3

3

5 B
6 R
3

0

Các số nguyên dương từ \(1\) đến \(n\) được ghi trên một đường tròn theo chiều kim đồng hồ. Các cung bằng nhau được chia bằng các số liên tiếp từ số đầu tiên đến số cuối cùng (Hình dưới). Bắt đầu từ vị trí số \(1\), di chuyển trên đường tròn theo chiều kim đồng hồ qua \(d\) cung và dừng lại ở vị trí đã ghi số. Vị trí bắt đầu cũng được xem là một vị trí dừng. Mỗi lần di chuyển như vậy ta gọi là một bước nhảy. Chúng ta thực hiện \(k\) bước nhảy, bước nhảy tiếp theo bắt đầu từ vị trí dừng của bước nhảy trước đó.

Yêu cầu: hãy tính tổng các số tại mỗi vị trí dừng trong quá trình thực hiện \(k\) bước nhảy.

Input

• Một dòng ghi ba số nguyên dương \(n, d\) và \(k\) \((1 \leq n, d, k \leq 10^{3})\), các số ghi cách nhau dấu cách.

Output

• Một số nguyên dương là kết quả tìm được theo yêu cầu nêu trên.

Example

5 3 4

15

Hai số nguyên dương \(n\) và \(m\) gọi là hai số không tương đồng khi chúng khác nhau và không tồn tại hai số nguyên dương \(p\) và \(q\) (\(p \neq 1, q \neq 1\) và \(p \neq q\)) sao cho cả \(p\) và \(q\) đều là ước của \(n\) và \(m\). Ví dụ: \(6\) và \(8\) là hai số không tương đồng bới chúng chỉ có hai số \(1\) và \(2\) là ước của hai số (\(6\) và \(8\)), nhưng chỉ có một số khác \(1\); \(12\) và \(18\) không phải là hai số không tương đồng vì có đến ba số khác \(1\) là \(2, 3\) và \(6\) đều là ước của cả hai số.

Yêu cầu: Cho số \(n\) và hai số nguyên dương \(l, r\). Hãy tìm tất cả các số \(m\) với \((l \leq m \leq r)\) sao cho \(n\) và \(m\) là hai số không tương đồng.

Input

• Dòng đầu tiên chứa một số nguyên dương \(n\) \((1 \leq n \leq 10^{9})\).
• Dòng thứ hai ghi hai số nguyên dương \(l, r\) \((1 \leq l \leq r \leq 10^{9}, r − l \leq 1000)\).

Output

• Dòng thứ nhất ghi số nguyên dương \(k\) là số lượng các số \(m\) không tương đồng với \(n\) trong đoạn nguyên từ \(l\) đến \(r\).
• Dòng thứ hai ghi \(k\) số nguyên dương, các số ghi cách nhau dấu cách, là các số không tương đồng với \(n\) tìm được ghi theo thứ tự tăng

Scoring

• Subtask \(1\) (\(35\%\) số điểm): \(n, r \leq 100\).
• Subtask \(2\) (\(65\%\) số điểm): không có ràng buộc gì thêm.

Example

6
8 12

4
8 9 10 11

Cho dãy số gồm \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\). Xuất phát từ dãy ban đầu, ta thực hiện \(q\) lần một trong hai loại phép toán sau trên các dãy thu được.

1. Thay phần từ thứ \(i\) của dãy bằng giá trị \(x\).
2. Dịch dãy sang phải \(k\) vị trí, nếu dãy hiện tại là \(a_{1}, a_{2}, \ldots, a_{n}\) thì sau khi dịch sẽ là dãy: \(a_{n - k + 1}, a_{n - k + 2}, \ldots, a_{n}, a_{1}, a_{2}, \ldots, a_{n - k}\).

Yêu cầu: Sau mỗi lần thực hiện phép toán loại \(1\), hãy tính tổng giá trị các phần tử của dãy thu được.

Input

• Dòng thứ nhất ghi số nguyên dương \(n\) \((2 \leq n \leq 10^{5})\)
• Dòng thứ hai ghi \(n\) số nguyên, các số ghi cách nhau dấu cách là giá trị của các số hạng của dãy \(a_{1}, a_{2}, \ldots, a_{n}\) \((−10^{9} \leq a_{i} \leq 10^{9})\).
• Dòng thứ ba ghi số nguyên dương \(q\) \((1 \leq q \leq 10^{5})\) là số phép toán cần thực hiện.
• \(q\) dòng tiếp theo, mỗi dòng mô tả một phép toán, các giá trị ghi cách nau dấu cách:
  • \(1\) \(i\) \(x\) \((1 \leq i \leq n, −10^{9} \leq x \leq 10^{9})\): là phép toán loại \(1\).
  • \(2\) \(k\) \((1 \leq k \leq n)\): là phép toán loại \(2\)

Output

• Với mỗi phép toán loại \(1\) ghi ra một số nguyên trên một dòng là tổng các số hạng của dãy khi thực hiện phép toán, thứ tự các kết quả theo đúng thứ tự các phép toán loại \(1\) trong tệp dữ liệu vào. Biết rắng kết quả không vượt quá \(10^{18}\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 10^{3}\), chỉ gồm phép toán loại 1.
• Subtask \(2\) (\(40\%\) số điểm): \(n \leq 10^{3}\).
• Subtask \(3\) (\(40\%\) số điểm): không có ràng buộc gì thêm.

Example

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

14
3