JOI 2012 Final Camp - Ngày 4

Toàn bộ \(N\) thành viên của Ủy ban Olympic Tin học Nhật Bản, trong đó có chủ tịch K, cùng đến một nhà hàng Trung Hoa.

Bàn ăn là một chiếc bàn tròn với \(N\) chỗ ngồi cách đều nhau. Ở giữa bàn có một mâm xoay để đặt các món ăn. Các thành viên ngồi vào \(N\) chỗ; chủ tịch K được đánh số \(1\), các thành viên tiếp theo được đánh số \(2,3,\ldots,N\) theo chiều ngược kim đồng hồ.

Ủy ban gọi \(N\) món ăn khác nhau, mỗi món một phần, và đặt chúng trên mâm xoay. Ban đầu, món \(i\) nằm ngay trước mặt thành viên \(i\) với mọi \(1 \le i \le N\). Mỗi thành viên ngoài chủ tịch K đã chọn sẵn một món muốn ăn: thành viên \(i\) muốn ăn món \(A_i\), với \(2 \le i \le N\).

Mâm xoay có thể quay theo cả hai chiều, mỗi đơn vị quay là một góc:

Ví dụ, nếu quay mâm ngược chiều kim đồng hồ một đơn vị từ trạng thái ban đầu, món \(N\) sẽ ở trước mặt chủ tịch K, còn món \(i-1\) sẽ ở trước mặt thành viên \(i\) với \(2 \le i \le N\). Một thành viên chỉ có thể ăn một món khi món đó nằm ngay trước mặt mình.

Vì chủ tịch K rất được kính trọng, ông là người đầu tiên quay mâm để món \(k\) (\(1 \le k \le N\)) đến trước mặt mình rồi ăn món đó. Sau khi chủ tịch ăn xong, các thành viên còn lại lần lượt quay mâm để món họ muốn ăn đến trước mặt mình rồi ăn. Thứ tự của các thành viên còn lại có thể tùy ý. Mỗi món đều có đủ thức ăn và không bao giờ hết.

Yêu cầu

Để chuẩn bị cho mọi lựa chọn của chủ tịch K, với mỗi \(k\) từ \(1\) đến \(N\), hãy tính tổng số đơn vị quay mâm nhỏ nhất để tất cả các thành viên đều được ăn món mình chọn. Tổng này bao gồm cả lần quay đầu tiên của chủ tịch K.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn:

• Dòng đầu tiên chứa số nguyên \(N\), là số thành viên.
• \(N-1\) dòng tiếp theo mô tả món ăn mà các thành viên muốn ăn. Dòng thứ \(i\) của dữ liệu vào (\(2 \le i \le N\)) chứa số nguyên \(A_i\).

Dữ liệu ra

In ra đầu ra chuẩn \(N\) dòng. Dòng thứ \(k\) (\(1 \le k \le N\)) chứa tổng số đơn vị quay mâm nhỏ nhất khi chủ tịch K chọn món \(k\). Một đơn vị quay tương ứng với góc \(360/N\) độ.

Ràng buộc

• \(2 \le N \le 100\,000\).
• \(1 \le A_i \le N\) với mọi \(2 \le i \le N\).

Phân nhóm

• Các bộ kiểm thử chiếm \(10\%\) tổng số điểm thỏa mãn \(N \le 10\).
• Các bộ kiểm thử chiếm \(40\%\) tổng số điểm thỏa mãn \(N \le 1\,000\).

Các tỉ lệ trên là các điều kiện tích lũy; không cộng chúng thành các nhóm điểm độc lập.

Ví dụ

5
3
5
3
2

4
4
5
6
4

Sao chép và dán là một trong những chức năng quan trọng nhất của trình soạn thảo văn bản. Công ty JOI bắt đầu phát triển một trình soạn thảo có thể xử lý các thao tác này rất nhanh. Là một lập trình viên giỏi của công ty, bạn được giao nhiệm vụ cài đặt phần xử lý cốt lõi. Tương lai của công ty phụ thuộc vào công việc này, nên bạn cần viết một chương trình vừa chính xác vừa nhanh.

Ban đầu, nội dung tệp là xâu \(S\). Sau đó, thực hiện \(N\) thao tác sao chép và dán. Trong thao tác thứ \(i\), sao chép đoạn xâu từ vị trí \(A_i\) đến vị trí \(B_i\), rồi chèn bản sao vào vị trí \(C_i\) của xâu hiện tại.

Ở đây, vị trí \(x\) là ranh giới ngay sau \(x\) ký tự đầu tiên của xâu; vị trí \(0\) là đầu xâu. Vì vậy, đoạn được sao chép gồm \(B_i-A_i\) ký tự nằm giữa hai ranh giới \(A_i\) và \(B_i\). Các vị trí \(A_i\), \(B_i\), \(C_i\) đều được xác định trên xâu ngay trước thao tác; việc sao chép không xóa đoạn gốc.

Nếu sau khi chèn, độ dài xâu vượt quá \(M\), xóa các ký tự từ cuối xâu cho đến khi độ dài còn đúng \(M\).

Yêu cầu

Cho giới hạn độ dài \(M\), xâu ban đầu \(S\) và thông tin của \(N\) thao tác, hãy tìm xâu thu được sau tất cả các thao tác.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn:

• Dòng đầu tiên chứa số nguyên \(M\), là giới hạn độ dài xâu.
• Dòng thứ hai chứa xâu \(S\) ban đầu.
• Dòng thứ ba chứa số nguyên \(N\), là số thao tác.
• Dòng thứ \(i+3\) (\(1 \le i \le N\)) chứa ba số nguyên \(A_i\), \(B_i\), \(C_i\), cách nhau bởi dấu cách, mô tả thao tác thứ \(i\).

Dữ liệu ra

In ra đầu ra chuẩn một dòng chứa xâu thu được sau \(N\) thao tác.

Ràng buộc

• \(1 \le M \le 1\,000\,000\).
• \(1 \le N \le 1\,000\,000\).
• \(S\) chỉ gồm các chữ cái Latin thường và có độ dài từ \(1\) đến \(M\).
• Gọi \(L_i\) là độ dài xâu ngay trước thao tác thứ \(i\). Với mọi \(1 \le i \le N\), có \(0 \le A_i < B_i \le L_i\) và \(0 \le C_i \le L_i\).

Phân nhóm

• Các bộ kiểm thử chiếm \(10\%\) tổng số điểm thỏa mãn \(M \le 100\,000\) và \(N \le 100\,000\).

Ví dụ

18
copypaste
4
3 6 8
1 5 2
4 12 1
17 18 0

acyppypastoopyppyp

100
joi
3
0 1 0
3 4 3
2 3 3

jjooii

Năm 20XX, kỳ thi IOI cuối cùng cũng được tổ chức tại thị trấn JOI của đất nước JOI. Một bữa tiệc sẽ được tổ chức để kỷ niệm sự kiện này. Thị trấn có \(A\) con chó được đánh số từ \(1\) đến \(A\) và \(B\) con mèo được đánh số từ \(1\) đến \(B\). Bạn muốn mời cả \(A+B\) con vật đến dự tiệc.

Giữa những con chó và mèo có \(N\) nhóm bạn thân. Nhóm thứ \(i\) gồm tất cả \(Q_i-P_i+1\) con chó có số hiệu từ \(P_i\) đến \(Q_i\) và tất cả \(S_i-R_i+1\) con mèo có số hiệu từ \(R_i\) đến \(S_i\). Nhóm này có độ thân thiết là số nguyên dương \(T_i\). Một con vật có thể thuộc nhiều nhóm hoặc không thuộc nhóm nào.

Bạn rất thân với con chó số \(C\) và đã mời thành công con chó đó. Bạn sẽ lặp lại quy trình sau để mời những con vật còn lại:

1. Nếu đã mời thành công cả \(A+B\) con vật thì kết thúc.
2. Tính giá trị hạnh phúc khi mời từng con vật chưa được mời. Xét các nhóm mà con vật đó thuộc về và đã có ít nhất một con chó hoặc mèo được mời thành công. Giá trị hạnh phúc là độ thân thiết lớn nhất trong các nhóm như vậy. Nếu không có nhóm nào thỏa mãn, giá trị hạnh phúc bằng \(0\).
3. Chọn con vật có giá trị hạnh phúc lớn nhất. Nếu có nhiều con như vậy, ưu tiên chó hơn mèo; nếu vẫn còn nhiều lựa chọn, ưu tiên con có số hiệu nhỏ hơn.
4. Nếu giá trị hạnh phúc của con vật được chọn bằng \(0\), việc mời thất bại và quy trình kết thúc. Ngược lại, bạn mời thành công con vật đó rồi tiếp tục quy trình.

Yêu cầu

Cho \(A\), \(B\), \(C\) và thông tin của \(N\) nhóm bạn thân, hãy xác định liệu có mời thành công tất cả các con vật hay không. Nếu có, hãy tính tổng giá trị hạnh phúc của những con vật được chọn qua các bước của quy trình. Con chó số \(C\) đã được mời từ trước nên không đóng góp vào tổng này.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn:

• Dòng đầu tiên chứa ba số nguyên \(A\), \(B\), \(C\), lần lượt là số con chó, số con mèo và số hiệu con chó đã được mời.
• Dòng thứ hai chứa số nguyên \(N\), là số nhóm bạn thân.
• Dòng thứ \(i+2\) (\(1 \le i \le N\)) chứa năm số nguyên \(P_i\), \(Q_i\), \(R_i\), \(S_i\), \(T_i\), cách nhau bởi dấu cách, mô tả nhóm thứ \(i\).

Dữ liệu ra

In ra đầu ra chuẩn một dòng chứa một số nguyên:

• Nếu mời thành công cả \(A+B\) con vật, in tổng giá trị hạnh phúc của các con vật được chọn qua các bước của quy trình.
• Nếu việc mời thất bại giữa chừng, in \(-1\).

Ràng buộc

• \(1 \le A \le 1\,000\,000\,000\).
• \(1 \le B \le 1\,000\,000\,000\).
• \(1 \le C \le A\).
• \(1 \le N \le 100\,000\).
• \(1 \le P_i \le Q_i \le A\) với mọi \(1 \le i \le N\).
• \(1 \le R_i \le S_i \le B\) với mọi \(1 \le i \le N\).
• \(1 \le T_i \le 1\,000\,000\,000\) với mọi \(1 \le i \le N\).

Phân nhóm

• Các bộ kiểm thử chiếm \(30\%\) tổng số điểm thỏa mãn \(A \le 1\,000\), \(B \le 1\,000\) và \(N \le 2\,000\).
• Các bộ kiểm thử chiếm \(50\%\) tổng số điểm thỏa mãn \(N \le 2\,000\).

Các tỉ lệ trên là các điều kiện tích lũy; không cộng chúng thành các nhóm điểm độc lập.

Ví dụ

5 6 3
4
2 4 1 3 20
1 2 2 4 40
4 5 2 3 30
4 4 4 6 10

280

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

-1