Một nhóm tuần lộc được chọn để kéo xe trượt tuyết. Mỗi con tuần lộc có một tên (chuỗi ký tự, \(\le 20\) chữ cái, phân biệt chữ hoa/thường), một thâm niên và một năng suất (cả hai là số nguyên dương \(\le 10^6\)).

Khi kéo xe, chúng xếp thành một hàng, luôn theo thứ tự thâm niên giảm dần từ trước ra sau. (Đề bài đảm bảo không có hai con tuần lộc nào có cùng thâm niên).

Năng suất của một cặp tuần lộc liền kề trong hàng là tích của hai năng suất cá nhân của chúng.
Tổng năng suất của cả hàng là tổng năng suất của tất cả các cặp liền kề.
(Nếu hàng có 0 hoặc 1 con, tổng năng suất là 0).

Ban đầu hàng trống. Santa sẽ thực hiện \(M\) (\(1 \le M \le 10^5\)) thao tác:

• A name S P: Thêm một con tuần lộc mới (tên name, thâm niên \(S\), năng suất \(P\)) vào hàng. Nó sẽ được chèn vào vị trí chính xác để duy trì thứ tự thâm niên giảm dần. (Đảm bảo mỗi con chỉ được thêm 1 lần).
• R name: Xóa con tuần lộc có tên name khỏi hàng. (Đảm bảo con này đang có trong hàng).

Bạn cần tính và in ra tổng năng suất của hàng sau mỗi thao tác.

Input

• Dòng đầu tiên chứa số nguyên \(M\).
• \(M\) dòng tiếp theo, mỗi dòng là một thao tác có dạng A name S P hoặc R name.

Output

• In ra \(M\) dòng. Dòng thứ \(i\) là tổng năng suất của hàng sau thao tác thứ \(i\).

Examples

5
A Dancer 5 2
A Prancer 3 8
A Vixen 10 9
R Dancer
A Rudolph 1 1

0
16
34
72
80

Cho dãy gồm \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\). Hiệp đố Đức Anh tính số cách chọn ra một dãy con (không cần liên tiếp) có tổng bằng \(k\) trong dãy trên, Đức Anh khôn nên giải trong đúng \(36\) giây. Hiệp lại tăng độ khó, Hiệp hỏi \(q\) truy vấn \(l, r, k\) với ý nghĩa tính số cách chọn một dãy con có tổng bằng \(k\) trong dãy \(a_l, a_{l + 1}, \ldots, a_r\). Đức Anh gà nên nhờ bạn giúp, hãy giúp anh ấy.

Input

• Dòng đầu là hai số nguyên dương \(n\) và \(q\) \((1 \le n, q \le 10^5)\).
• Dòng thứ hai là \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((0 \le a_i \le 100)\).
• \(q\) dòng tiếp theo, mỗi dòng là ba số nguyên dương \(l, r, k\) thể hiện một truy vấn \((1 \le l \le r \le n, k \le 100)\).

Output

• \(q\) dòng là đáp án cho \(q\) truy vấn, lấy dư cho \(10^9 + 7\).

Example

5 3
1 9 8 1 2
1 5 2
1 4 10
1 5 3

2
3
2

Cho một mảng 2 chiều (ma trận) \(A\) gồm \(n\) dòng và \(m\) cột. Có \(q\) truy vấn, mỗi truy vấn thuộc một trong 2 dạng sau:

• 1 i j: Đổi chỗ hàng \(i\) và hàng \(j\).
• 2 i j: Đổi chỗ cột \(i\) và cột \(j\).

In ra ma trận \(A\) sau khi thực hiện \(q\) thao tác. Các chỉ số hàng và cột được đánh số từ \(1\).

Input

• Dòng đầu tiên chứa 3 số nguyên \(n, m, q\) (\(1 \le n, m, q \le 100\)).
• \(n\) dòng tiếp theo, mỗi dòng chứa \(m\) số nguyên, thể hiện ma trận \(A\) (\(|A_{i,j}| \le 100\)).
• \(q\) dòng tiếp theo, mỗi dòng là một truy vấn có dạng 1 i j (đổi hàng) hoặc 2 i j (đổi cột). Các chỉ số \(i, j\) là hợp lệ.

Output

• In ra \(n\) dòng, mỗi dòng chứa \(m\) số nguyên, thể hiện ma trận \(A\) sau khi thực hiện \(q\) truy vấn. Các số trên cùng một dòng cách nhau bởi dấu cách.

Examples

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

7 8 9
4 5 6
1 2 3

1 2 3
4 5 6
7 8 9

7 8 9
4 5 6
1 2 3

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

6 5 4
3 2 1

1 2 3
4 5 6

3 2 1
6 5 4

6 5 4
3 2 1

Cho một bảng (ma trận) \(A\) kích thước \(n \times m\) (gồm \(n\) hàng và \(m\) cột) chứa các phần tử nguyên. Hãy xoay bảng này \(90\) độ theo chiều kim đồng hồ.

Lưu ý: Sau khi xoay, bảng mới sẽ có kích thước \(m \times n\) (\(m\) hàng và \(n\) cột).

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) (\(1 \le n, m \le 50\)).
• \(n\) dòng tiếp theo, mỗi dòng chứa \(m\) số nguyên \(A_{i,j}\) (\(1 \le A_{i,j} \le 100\)), là các phần tử của bảng.

Output

• In ra \(m\) dòng, mỗi dòng chứa \(n\) số nguyên, là bảng đã được xoay. Các số trên cùng một dòng cách nhau bởi dấu cách.

Examples

3 2
1 2
3 4
5 6

5 3 1
6 4 2

2 4
1 2 3 4
5 6 7 8

5 1
6 2
7 3
8 4