Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 1G

Điểm: 100

Tại một thành phố nọ, có một dãy gồm ~n~ bức tường hình chữ nhật nằm liền kề nhau, không có khoảng trống và có cạnh dưới cùng nằm trên một đường thẳng nằm ngang. Các bức tường được đánh số từ ~1~ đến ~n~ theo thứ tự từ trái sang phải. Bức tường thứ ~i~ có chiều rộng ~w_i~ và chiều cao ~h_i~.

Trong khi người qua đường chỉ thấy một dãy tường, Shidou lại thấy cơ hội khởi nghiệp. Cậu lập tức thuê toàn bộ mặt tường, quyết tâm phủ kín nó bằng poster quảng cáo. Theo kế hoạch, đây sẽ là bước đầu tiên để xây dựng một đế chế quảng cáo.

Vấn đề là mỗi tấm poster đều tốn tiền. Dãy tường thì dài, ngân sách thì hạn hẹp, nên Shidou phải tìm cách dùng ít poster nhất có thể mà vẫn phủ kín toàn bộ mặt tường.

Việc dán poster phải tuân thủ các quy định sau:

  • Mỗi poster là một hình chữ nhật có kích thước tùy ý, với các cạnh nằm ngang hoặc thẳng đứng.

  • Một poster có thể phủ qua nhiều bức tường liền kề, nhưng phải nằm hoàn toàn trong mặt tường.

  • Các poster không được chồng lên nhau, nhưng có thể chạm nhau hoặc dùng chung cạnh.

  • Tất cả các poster phải cùng nhau phủ kín toàn bộ mặt tường.

Hãy tính số lượng poster ít nhất mà Shidou cần sử dụng, để đế chế quảng cáo kịp ra đời trước khi founder phải đi xin hoàn tiền thuê tường.

Input

Dòng đầu tiên chứa số nguyên ~n~ (~1 \leq n \leq 10^6~) — số lượng bức tường trong dãy tường.

Mỗi dòng trong ~n~ dòng tiếp theo chứa ~w_i, h_i~ (~1 \leq w_i, h_i \leq 10^9~) lần lượt là chiều rộng và chiều cao của bức tường thứ ~i~.

Output

In ra một số nguyên duy nhất là số lượng poster ít nhất cần phải sử dụng.

Sample Input 1

5
1 2
1 3
2 2
2 5
1 4

Sample Output 1

4

Notes

image

Hình trên thể hiện chiều rộng và chiều cao của các bức tường trong ví dụ. Hình dưới minh họa cách phủ kín dãy tường bằng ~4~ tấm poster.


Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 1G

Điểm: 100

Pengin là điệp viên của một tổ chức tình báo. Tổ chức phát hiện ~N~ máy chủ bị nhiễm mã độc. Máy chủ thứ ~i~ có mức độ nguy hiểm là ~A_i~ và hạn chót để xử lý là ~D_i~.

Mỗi ngày, Pengin chỉ có thể xử lý triệt để duy nhất một máy chủ. Nếu máy chủ ~i~ được xử lý tại ngày ~t~, Pengin sẽ nhận được số điểm uy tín là ~A_i~, với điều kiện ~t \le D_i~. Nếu ~t > D_i~, máy chủ đó tự hủy và Pengin không nhận được điểm.

Tuy nhiên, Pengin có ~K~ "Thiết bị đóng băng". Mỗi thiết bị chỉ dùng được một lần. Khi dùng một thiết bị, Pengin xử lý một máy chủ bất kỳ mà không tiêu tốn thời gian của ngày đó, tức là ngày hôm đó Pengin vẫn có thể xử lý thêm một máy chủ khác theo cách bình thường. Pengin có thể dùng nhiều thiết bị trong cùng một ngày.

Hãy tìm tổng số điểm uy tín lớn nhất có thể đạt được, xuất phát với thời gian ~t = 1~.

Input

Dòng thứ nhất chứa hai số nguyên ~N~ và ~K~ (~1 \le N \le 2 \cdot 10^5~, ~0 \le K \le N~).

Mỗi dòng trong ~N~ dòng tiếp theo chứa hai số nguyên ~A_i~ và ~D_i~ (~1 \le A_i \le 10^9~, ~1 \le D_i \le N~).

Output

Một số nguyên duy nhất là tổng điểm lớn nhất thu được.

Scoring

Subtask Điểm Giới hạn
1 ~15~ ~N \le 10~, ~K = 0~
2 ~20~ ~N \le 2000~, ~K = 0~
3 ~25~ ~K = 0~
4 ~20~ ~N \le 2000~
5 ~20~ Không có ràng buộc gì thêm

Sample Input 1

6 2
100 1
20 1
80 2
90 2
40 3
10 1

Sample Output 1

330

Notes

Trong các ngày ~1~, ~2~, ~3~, Pengin xử lý các máy chủ có điểm ~100~, ~90~, ~40~. Hai thiết bị đóng băng dùng cho các máy chủ có điểm ~80~ và ~20~. Tổng là ~330~.


Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 1G

Điểm: 100

Cho một dãy ~w~ gồm ~n~ số nguyên dương. Bạn được chọn một đoạn liên tiếp có độ dài không quá ~d~ và gán mọi phần tử trong đoạn đó bằng ~0~. Sau đó, hãy tìm độ dài lớn nhất của một đoạn con liên tiếp có tổng không quá ~p~.

Input

Dòng đầu tiên chứa ba số nguyên ~n~, ~p~ và ~d~ (~1 \le d \le n \le 2 \cdot 10^6~, ~0 \le p \le 10^{16}~).

Dòng thứ hai chứa ~n~ số nguyên ~w_1, w_2, \ldots, w_n~ (~1 \le w_i \le 10^9~).

Output

Một số nguyên duy nhất là độ dài lớn nhất của đoạn con tìm được.

Sample Input 1

9 7 2
3 4 1 9 4 1 7 1 3

Sample Output 1

5

Notes

Gán ~w_4 = w_5 = 0~. Đoạn từ vị trí ~2~ đến vị trí ~6~ có tổng ~4 + 1 + 0 + 0 + 1 = 6 \le 7~ và độ dài ~5~.


Giới hạn thời gian: 1.25s / Giới hạn bộ nhớ: 1G

Điểm: 100

Ai cũng biết, không dùng đến một cây thép ren kết hợp với dây cáp hãm đà tàu sân bay để làm cần câu thì làm sao có thể câu được con quái vật khổng lồ nặng hàng trăm triệu cân.

Mathduck là một người bỏ code để đi câu cá. Vào một ngày đi câu cá trong lễ hội trung thu, ông câu được ~n~ con cá, con cá thứ ~i~ có cân nặng là ~a_i~. Để kết thúc một ngày câu cá hiệu quả, ông quyết định thực hiện ~q~ thao tác, mỗi thao tác thuộc một trong ba loại sau:

  • 1 x: Mathduck câu thêm một con cá có cân nặng ~x~.

  • 2 x: Mathduck bán đi một con cá có cân nặng ~x~. Dữ liệu đảm bảo tồn tại ít nhất một con cá có cân nặng ~x~.

  • 3 w: với mỗi con cá có cân nặng ~x \ge w~, Mathduck cắt bớt để cân nặng của nó còn ~x \bmod w~.

Sau mỗi thao tác, Mathduck cần tính tổng cân nặng của tất cả các con cá mà ông còn giữ.

Input

Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ (~1 \le n, q \le 2 \cdot 10^5~).

Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le 10^9~).

Mỗi dòng trong ~q~ dòng tiếp theo mô tả một thao tác, có dạng 1 x, 2 x hoặc 3 w (~1 \le x, w \le 10^9~).

Output

In ra ~q~ dòng. Dòng thứ ~i~ chứa tổng cân nặng các con cá mà Mathduck còn giữ sau thao tác thứ ~i~.

Scoring

Subtask Điểm Giới hạn
1 ~20~ ~n, q, a_i, x, w \le 1000~
2 ~20~ Không có truy vấn loại ~3~
3 ~20~ Mọi truy vấn loại ~3~ có ~w \ge \lfloor M / 2 \rfloor~, với ~M~ là giá trị lớn nhất của mảng ~a~ ban đầu
4 ~40~ Không có ràng buộc gì thêm

Sample Input 1

4 5
5 8 12 15
3 6
1 10
3 4
2 2
3 2

Sample Output 1

10
20
8
6
2

Notes

Ban đầu, cân nặng các con cá là ~\{5, 8, 12, 15\}~, tổng là ~40~.

  • Truy vấn ~1~ (3 6): các con cá nặng ít nhất ~6~ là ~8~, ~12~, ~15~. Ta có ~8 \bmod 6 = 2~, ~12 \bmod 6 = 0~, ~15 \bmod 6 = 3~. Tập mới là ~\{5, 2, 0, 3\}~, tổng là ~10~.

  • Truy vấn ~2~ (1 10): thêm một con cá nặng ~10~. Tập mới là ~\{5, 2, 0, 3, 10\}~, tổng là ~20~.

  • Truy vấn ~3~ (3 4): ~5 \bmod 4 = 1~ và ~10 \bmod 4 = 2~. Tập mới là ~\{1, 2, 0, 3, 2\}~, tổng là ~8~.

  • Truy vấn ~4~ (2 2): bán một con cá nặng ~2~. Tập mới là ~\{1, 0, 3, 2\}~, tổng là ~6~.

  • Truy vấn ~5~ (3 2): ~3 \bmod 2 = 1~ và ~2 \bmod 2 = 0~. Tập mới là ~\{1, 0, 1, 0\}~, tổng là ~2~.


Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 1G

Điểm: 100

Davele có ~N~ công việc. Công việc ~i~ cần ~S_i~ đơn vị thời gian và không được thực hiện trước thời điểm ~T_i~. Có thể tạm dừng rồi tiếp tục công việc, tuy nhiên tại mỗi thời điểm chỉ được thực hiện nhiều nhất một công việc. Gọi ~C_i~ là thời điểm hoàn thành công việc ~i~. Hãy tìm giá trị nhỏ nhất của ~\sum_{i=1}^{N} C_i~.

Input

Dòng đầu tiên chứa số nguyên ~N~ (~1 \le N \le 2 \cdot 10^5~).

Mỗi dòng trong ~N~ dòng tiếp theo chứa hai số nguyên ~T_i~ và ~S_i~ (~0 \le T_i \le 10^9~, ~1 \le S_i \le 10^6~).

Output

Một dòng chứa giá trị nhỏ nhất của ~\sum_{i=1}^{N} C_i~.

Scoring

Subtask Điểm Giới hạn
1 ~10~ ~N \le 2~
2 ~20~ ~T_1 = T_2 = \cdots = T_N~
3 ~20~ ~S_1 = S_2 = \cdots = S_N~
4 ~50~ Không có ràng buộc gì thêm

Sample Input 1

2
0 10
5 3

Sample Output 1

21

Notes

Làm công việc ~1~ từ thời điểm ~0~ đến thời điểm ~5~. Công việc ~2~ bắt đầu ở thời điểm ~5~ và xong ở thời điểm ~8~. Sau đó công việc ~1~ làm tiếp và xong ở thời điểm ~13~. Tổng là ~8 + 13 = 21~.


Giới hạn thời gian: 2.0s / Giới hạn bộ nhớ: 1G

Điểm: 100

Shark Davele đang lập kế hoạch đầu tư mở rộng chuỗi kinh doanh taxi điện Velefast sang đất nước B-Land. Đất nước này có cấu trúc địa lý rất đặc biệt: gồm ~N~ tỉnh thành được sắp xếp nối tiếp nhau trên một đường thẳng, được đánh số từ ~1~ đến ~N~. Tỉnh thành thứ ~i~ có mật độ dân số được định lượng là ~A_i~.

Để tối ưu hóa chi phí hậu cần và vận hành:

  1. Quy mô dự án không thể quá nhỏ cũng không thể quá lớn, và cũng không thể rời rạc (vì khó quản lý). Do đó, Davele bắt buộc phải lựa chọn kinh doanh taxi tại một chuỗi các tỉnh thành liên tiếp nhau từ tỉnh ~i~ đến tỉnh ~j~ có số lượng tỉnh thuộc đoạn ~[L, R]~ (tức là ~L \le j - i + 1 \le R~).

  2. Để đảm bảo doanh thu và quy mô thị trường mục tiêu tốt nhất, Davele muốn chọn khu vực sao cho mật độ dân số trung bình của các tỉnh được chọn đạt giá trị lớn nhất.

Hãy giúp Davele tính toán mật độ dân số trung bình lớn nhất có thể đạt được để đưa ra quyết định đầu tư chính xác nhất!

Input

Dòng đầu tiên chứa ba số nguyên ~N~, ~L~ và ~R~ (~1 \le L \le R \le N \le 10^6~).

Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2, \ldots, A_N~ (~1 \le A_i \le 10^9~).

Output

In ra một số thực là mật độ dân số trung bình lớn nhất tìm được. Kết quả được chấp nhận nếu có sai số tuyệt đối hoặc tương đối không vượt quá ~10^{-4}~.

Scoring

Subtask Điểm Giới hạn
1 ~30~ ~N \le 5000~
2 ~30~ ~N \le 2 \cdot 10^5~
3 ~40~ Không có ràng buộc gì thêm

Sample Input 1

5 2 3
1 2 4 3 5

Sample Output 1

4.000000000

Notes

Ta chọn các tỉnh từ ~3~ đến ~5~. Mật độ trung bình là ~\frac{4 + 3 + 5}{3} = 4~.


Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 1G

Điểm: 100

Kỳ thi tuyển sinh lớp 10 vừa kết thúc, ~N~ thí sinh đã nộp bài thành một xấp. Các bài thi có số báo danh từ ~1~ đến ~N~, mỗi số xuất hiện đúng một lần. Theo quy chế, bài thi phải được cho vào túi niêm phong theo đúng thứ tự: bài có số báo danh nhỏ nhất nằm dưới đáy túi, bài có số báo danh lớn nhất nằm trên cùng.

Việc xếp bài được giao cho hai giám thị là thầy Quân và thầy Trọng. Thầy Trọng ngồi ở đầu bàn bên trái, ngay cạnh túi niêm phong, và vì đã ngồi canh thi suốt ba tiếng nên thầy nhất quyết không đứng dậy. Thầy Quân cầm xấp bài vừa thu trên tay, đứng ở đầu bên kia và xếp tạm bài thành các chồng dọc theo mặt bàn.

Ở mỗi bước, một trong hai việc sau được thực hiện:

  • Thầy Quân lấy bài trên cùng của xấp bài vừa thu, kiểm tra chữ ký rồi đặt lên bàn theo một trong hai cách: đặt lên trên một chồng bài đang có trên bàn, hoặc tạo một chồng mới nằm bên phải tất cả các chồng hiện có.

  • Thầy Trọng lấy bài trên cùng của chồng ngoài cùng bên trái và cho vào túi niêm phong, nằm trên tất cả các bài đã có trong túi. Nếu chồng đó hết bài, nó biến mất khỏi bàn.

Hai thầy được tự do chọn thứ tự thực hiện các bước.

Tất nhiên, không phải lúc nào hai thầy cũng xếp được cả ~N~ bài. Khi đó, hai thầy sẽ chỉ xử lý một số bài trên cùng của xấp bài vừa thu, còn những bài bên dưới để nguyên và giao lại cho hội đồng thi.

Hai thầy muốn xử lý được càng nhiều bài càng tốt. Hãy tìm số ~k~ lớn nhất sao cho hai thầy có thể cho hết ~k~ bài trên cùng vào túi, sao cho số báo danh tăng dần từ đáy túi lên trên.

Input

  • Dòng đầu tiên chứa số nguyên ~N~ (~1 \le N \le 10^5~).

  • Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, \ldots, a_N~ là một hoán vị của ~1, 2, \ldots, N~, trong đó ~a_1~ là số báo danh của bài nằm trên cùng xấp bài vừa thu.

Output

In ra số nguyên ~k~ lớn nhất thỏa mãn.

Scoring

Subtask Điểm Giới hạn
1 ~20~ ~N \le 10~
2 ~30~ ~N \le 5000~
3 ~50~ Không có ràng buộc gì thêm

Sample Input 1

5
4 5 2 3 1

Sample Output 1

4

Sample Input 2

4
3 4 1 2

Sample Output 2

4

Notes

Giải thích ví dụ 1. Thầy Quân đặt bài ~4~ (chồng mới), bài ~5~ (chồng mới bên phải), rồi bài ~2~ lên trên bài ~4~. Thầy Trọng cho bài ~2~ vào túi. Thầy Quân đặt bài ~3~ lên trên bài ~4~. Thầy Trọng lần lượt cho bài ~3, 4, 5~ vào túi. Túi chứa ~2, 3, 4, 5~ (từ dưới lên), đúng thứ tự. Không thể xếp thêm bài ~1~ vì bài ~2~ đã nằm trong túi, nên hai thầy xử lý ~4~ bài trên cùng và bài ~1~ được giao lại cho hội đồng thi.

Trong các bảng dưới đây, mỗi chồng trên bàn và túi niêm phong đều được ghi từ dưới lên.

Lượt Người Thao tác Các chồng trên bàn (trái sang phải) Túi niêm phong
1 Thầy Quân Đặt bài ~4~ thành chồng mới ~[4]~ (trống)
2 Thầy Quân Đặt bài ~5~ thành chồng mới ~[4]~ ~[5]~ (trống)
3 Thầy Quân Đặt bài ~2~ lên chồng thứ nhất ~[4, 2]~ ~[5]~ (trống)
4 Thầy Trọng Cho bài ~2~ vào túi ~[4]~ ~[5]~ ~2~
5 Thầy Quân Đặt bài ~3~ lên chồng thứ nhất ~[4, 3]~ ~[5]~ ~2~
6 Thầy Trọng Cho bài ~3~ vào túi ~[4]~ ~[5]~ ~2, 3~
7 Thầy Trọng Cho bài ~4~ vào túi ~[5]~ ~2, 3, 4~
8 Thầy Trọng Cho bài ~5~ vào túi (trống) ~2, 3, 4, 5~

Giải thích ví dụ 2. Thầy Quân đặt bài ~3~ (chồng mới), bài ~4~ (chồng mới bên phải), rồi bài ~1~ lên trên bài ~3~. Thầy Trọng cho bài ~1~ vào túi. Thầy Quân đặt bài ~2~ lên trên bài ~3~. Thầy Trọng lần lượt cho bài ~2, 3, 4~ vào túi. Túi chứa ~1, 2, 3, 4~ (từ dưới lên), đúng thứ tự, nên hai thầy xử lý được cả ~4~ bài. Lưu ý nếu chỉ dùng một chồng trên bàn, bài ~3~ phải được cho vào túi trước khi đặt bài ~4~, khi đó bài ~1~ sẽ không thể xếp được nữa.

Lượt Người Thao tác Các chồng trên bàn (trái sang phải) Túi niêm phong
1 Thầy Quân Đặt bài ~3~ thành chồng mới ~[3]~ (trống)
2 Thầy Quân Đặt bài ~4~ thành chồng mới ~[3]~ ~[4]~ (trống)
3 Thầy Quân Đặt bài ~1~ lên chồng thứ nhất ~[3, 1]~ ~[4]~ (trống)
4 Thầy Trọng Cho bài ~1~ vào túi ~[3]~ ~[4]~ ~1~
5 Thầy Quân Đặt bài ~2~ lên chồng thứ nhất ~[3, 2]~ ~[4]~ ~1~
6 Thầy Trọng Cho bài ~2~ vào túi ~[3]~ ~[4]~ ~1, 2~
7 Thầy Trọng Cho bài ~3~ vào túi ~[4]~ ~1, 2, 3~
8 Thầy Trọng Cho bài ~4~ vào túi (trống) ~1, 2, 3, 4~


Giới hạn thời gian: 2.0s / Giới hạn bộ nhớ: 512M

Điểm: 100

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Sample Input 1

11 10
1 0 1 F
1 2 10 C
1 3 8 W
1 9 9 M
1 4 6 M
2 2
2 1
2 5
1 5 7 C
2 1

Sample Output 1

1
4
0
3

Sample Input 2

12 5
1 3 7 G
1 7 11 G
1 4 5 C
1 0 6 C
2 2

Sample Output 2

8

Giới hạn thời gian: 0.5s / Giới hạn bộ nhớ: 1G

Điểm: 100

Ai cũng biết rằng ChrisDxng có hàng rào đẹp nhất trong toàn thị trấn. Nó được xây dựng từ ~N~ đoạn liền kề. Các đoạn này là các hình chữ nhật đứng sát cạnh nhau trên mặt đất. Đoạn thứ ~i~ có chiều cao là số nguyên ~h_i~ và chiều rộng là số nguyên ~w_i~.

Chúng ta cần tìm các hình chữ nhật "hợp lệ" trên hàng rào này. Một hình chữ nhật được coi là hợp lệ nếu thỏa mãn các điều kiện sau:

  • Các cạnh của nó nằm ngang hoặc thẳng đứng và có độ dài là một số nguyên.

  • Khoảng cách giữa cạnh dưới của hình chữ nhật và mặt đất là một số nguyên.

  • Khoảng cách giữa cạnh trái của hình chữ nhật và cạnh trái của đoạn hàng rào đầu tiên là một số nguyên.

  • Hình chữ nhật nằm hoàn toàn bên trong các đoạn của hàng rào.

Hỏi có tổng cộng bao nhiêu hình chữ nhật hợp lệ? Vì số lượng này có thể rất lớn, hãy in ra kết quả modulo ~10^9 + 7~.

Input

Dòng đầu tiên chứa số nguyên ~N~ (~1 \le N \le 10^5~) — số lượng đoạn của hàng rào.

Dòng thứ hai chứa ~N~ số nguyên ~h_1, h_2, \ldots, h_N~ (~1 \le h_i \le 10^9~).

Dòng thứ ba chứa ~N~ số nguyên ~w_1, w_2, \ldots, w_N~ (~1 \le w_i \le 10^9~).

Output

In ra một số nguyên duy nhất: số lượng hình chữ nhật hợp lệ modulo ~10^9 + 7~.

Scoring

Subtask Điểm Giới hạn
1 ~12~ ~N \le 50~, ~h_i \le 50~ và ~w_i = 1~ với mọi ~i~
2 ~13~ ~h_i \in \{1, 2\}~ với mọi ~i~
3 ~15~ ~h_1 = h_2 = \cdots = h_N~
4 ~15~ ~h_1 \le h_2 \le \cdots \le h_N~
5 ~18~ ~N \le 1000~
6 ~27~ Không có ràng buộc gì thêm

Sample Input 1

2
1 2
1 2

Sample Output 1

12

Notes

Có ~6~ hình chữ nhật hợp lệ nằm hoàn toàn ở độ cao từ ~0~ đến ~1~. Các hình chữ nhật còn lại phải nằm trong đoạn thứ hai và chạm độ cao ~2~. Có ~3~ hình như vậy cao ~1~ và ~3~ hình cao ~2~. Tổng là ~6 + 3 + 3 = 12~.


Giới hạn thời gian: 2.0s / Giới hạn bộ nhớ: 1G

Điểm: 100

Như các bạn đã biết, VNOI là 1 câu lạc bộ chuyên về Lập trình Thi đấu (Competitive Programming - CP). Vào năm 2050, khi Trí tuệ nhân tạo đã trở thành 1 phần trong đời sống thường ngày, một nhánh mới của CP chính là CP GBUP (Generating Box Units Programming) đã trở thành 1 trào lưu, thu hút các bạn trẻ khắp thế giới.

Quỳnh Anh và Khải Duy là 2 tuyển thủ top đầu thế giới ở bộ môn CP GBUP. Sau khi bị tổ chức 83.798u - liên đoàn thế giới ở bộ môn này - cấm thi đấu vĩnh viễn ở các giải đấu quốc tế vì quá out trình, hai bạn trẻ đã trở thành tình nguyện viên VNOI nhằm đóng góp cho cộng đồng lập trình thi đấu nước nhà. Đồng thời, 2 bạn cũng đã trở thành huấn luyện viên trưởng của đội tuyển Việt Nam tham dự CGS (CP-GPUB Global Series). Và để tập huấn đội tuyển, việc chuẩn bị cho nội dung thi đấu là vô cùng quan trọng.

Nhằm giúp các thành viên đội tuyển làm quen với những bài toán đặc trưng của CP GBUP, Quỳnh Anh và Khải Duy đã xây dựng một hệ thống mô phỏng bài thi đấu. Hệ thống gồm ~n~ hộp GBUP, được đánh số từ ~1~ đến ~n~. Mỗi hộp chứa một số xâu ma thuật và có thể thay đổi nội dung trong suốt quá trình tập luyện.

Một xâu ma thuật là một xâu mà tất cả các ký tự trong xâu chỉ gồm các kí tự trong bảng chữ cái tiếng Anh thường, tức là a, b, c, …, z

Ban đầu, hộp GBUP thứ ~i~ chứa ~n_i~ xâu ma thuật

Trong quá trình tập huấn, hệ thống sẽ nhận được ~q~ truy vấn thuộc một trong bốn loại sau:

  • ~1~ ~i~ ~s~: Thêm xâu ~s~ vào hộp GBUP thứ ~i~.
  • ~2~ ~i~ ~s~: Xóa một lần xuất hiện của xâu ~s~ khỏi hộp GBUP thứ ~i~. Dữ liệu đảm bảo xâu ~s~ hiện đang xuất hiện trong hộp ~i~.
  • ~3~ ~i~ ~j~: Lấy toàn bộ các xâu trong hộp thứ ~i~ và cho vào hộp thứ ~j~. Sau truy vấn này, hộp thứ ~i~ vẫn tồn tại, nhưng không chứa xâu nào (hộp thứ ~i~ vẫn có thể được thêm xâu trong tương lai).
  • ~4~ ~i~: Các vận động viên cần phải giải quyết bài toán sau:

Xét tất cả các xâu hiện có trong hộp GBUP thứ ~i.~ Sau khi sắp xếp các xâu theo thứ tự từ điển, ta thu được ~s_1,s_2,\ldots,s_k~, với k là số xâu trong hộp thứ ~k~.

Một cách chia hợp lệ là chọn một vị trí ~j~ thỏa mãn ~1 \le j \lt k~, sau đó chia dãy trên thành hai đoạn liên tiếp: ~s_1,s_2,\ldots,s_j~ và ~s_{j+1},s_{j+2},\ldots,s_k~.

Gọi ~L_c~ là số lần xuất hiện của kí tự ~c~ ở nửa trái, và ~R_c~ là số lần xuất hiện kí tự ~c~ ở nửa phải.

Độ cân bằng của một cách chia được định nghĩa là ~\left(\sum_{c} (ord(c)+1000)L_c\right) \left(\sum_{c} (ord(c)+1000)R_c\right)~.

Cần tìm độ cân bằng lớn nhất trong tất cả các cách chia hợp lệ cho bài toán này.

Lưu ý: ~ord(c)~ là số thứ tự của ~c~ trên bảng chữ cái. Ví dụ như ~ord(~a~) = 1~, ~ord(~z~) = 26~).

Bài toán này chắc chắn là quá dễ so với Quỳnh Anh và Khải Duy, tuy nhiên lại hơi khó với các vận động viên của chúng ta. Hãy giúp các bạn trong đội tuyển giải quyết bài toán này nhé!

Input

Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ thỏa mãn ~1\le n\le 5\cdot 10^4. 1 \le q \le 10^5~.

Dòng thứ ~i~ trong ~n~ dòng tiếp theo mô tả hộp GBUP thứ ~i~. Mỗi dòng trong ~n~ dòng này bắt đầu bằng một số nguyên ~n_i~, theo sau là ~n_i~ xâu ma thuật mô tả các xâu ban đầu trong hộp.

Dữ liệu đảm bảo rằng tổng độ dài xâu trong các tập hợp (tính cả các xâu ban đầu và các xâu được thêm vào) là không quá ~2 \cdot 10^5~

Sau đó là ~q~ dòng, mỗi dòng mô tả một truy vấn thuộc một trong ba loại đã nêu:

  • Đối với mỗi truy vấn loại 1 và loại 2, xâu ~s~ có độ dài từ 1 đến 12 và chỉ chứa các ký tự từ a đến z.
  • Đối với truy vấn loại 2, dữ liệu đảm bảo xâu s hiện đang xuất hiện trong hộp GBUP thứ ~i~.
  • Đối với mỗi truy vấn loại 3, dữ liệu đảm bảo ~i \neq j~.
  • Đối với mọi truy vấn loại 4, dữ liệu đảm bảo hộp ~i~ có ít nhất 2 phần tử.

Output

Với mỗi truy vấn loại 4, in ra một dòng chứa độ cân bằng lớn nhất có thể đạt được.

Scoring

Subtask Điểm Giới hạn
1 ~15~ ~n, q \le 100~
2 ~15~ ~n = 1~, chỉ có truy vấn loại ~4~
3 ~20~ ~n = 1~, không có truy vấn loại ~3~. Mỗi xâu được thêm vào không nhỏ hơn mọi xâu trong hộp theo thứ tự từ điển. Mỗi xâu bị xóa là xâu lớn nhất trong hộp
4 ~20~ ~n = 1~, không có truy vấn loại ~3~
5 ~30~ Không có ràng buộc gì thêm

Sample Input 1

2 6
2 adq vnq
0
1 2 dnpk
4 1
3 1 2
4 2
2 2 vnq
4 2

Sample Output 1

9226166
21575551
12223990

Notes

Truy vấn 2: Hộp 1 chứa hai xâu adq, vnq. Chỉ có một cách chia, cho độ cân bằng là ~3022 \times 3053 = 9226166~.

Truy vấn 4: Sau khi chuyển xâu từ hộp 1 sang hộp 2, các xâu được sắp xếp là adq, dnpk, vnq. Chia sau xâu dnpk cho độ cân bằng lớn nhất: ~(3022+4045)\times3053=21575551~.

Truy vấn 6: Sau khi xóa vnq, hộp 2 còn adq, dnpk. Độ cân bằng là ~3022\times4045=12223990~.