Năm 2016, tại Distributed Code Jam, chúng tôi đã giới thiệu ngôn ngữ Lisp++ dành cho những người hâm mộ Lisp thích mật độ dấu ngoặc cao hơn. Sau đây là phần nhắc lại về cú pháp của ngôn ngữ này.

Một chương trình Lisp++ là một chuỗi dấu ngoặc cân bằng. Chính xác hơn, một chương trình Lisp++ có một trong các dạng sau. (Trong đặc tả này, \(C\) biểu thị một đoạn mã chương trình nào đó — không nhất thiết là cùng một đoạn mã ở mỗi lần xuất hiện.)

• () — đúng nghĩa chỉ gồm một dấu ngoặc mở và một dấu ngoặc đóng. Ta nói dấu ( này khớp với dấu ) này, và ngược lại.
• (\(C\)) — một chương trình nằm bên trong một cặp dấu ngoặc bao ngoài. Ta nói dấu ( này khớp với dấu ) này, và ngược lại.
• \(CC\) — hai chương trình (không nhất thiết giống nhau) đặt liền nhau.

Năm nay, chúng tôi hân hạnh công bố Emacs++, một trình xem văn bản dành cho Lisp++. Emacs++ hiển thị một chương trình Lisp++ có độ dài \(K\) trên một dòng dài duy nhất, cùng một con trỏ mà bạn có thể di chuyển. Con trỏ là một "con trỏ khối", luôn nằm trên một trong \(K\) ký tự của chương trình chứ không nằm giữa hai ký tự.

Tại bất kỳ thời điểm nào, bạn có thể thực hiện một trong ba thao tác sau để di chuyển con trỏ. (\(i\) là vị trí hiện tại của con trỏ, đánh số từ 1 tại vị trí ngoài cùng bên trái.)

• Di chuyển con trỏ sang trái một ký tự (hoặc không làm gì nếu con trỏ đã ở ký tự ngoài cùng bên trái). Thao tác này mất \(L_i\) giây.
• Di chuyển con trỏ sang phải một ký tự (hoặc không làm gì nếu con trỏ đã ở ký tự ngoài cùng bên phải). Thao tác này mất \(R_i\) giây.
• Dịch chuyển tức thời con trỏ tới dấu ngoặc khớp (theo định nghĩa ở trên) với dấu ngoặc là ký tự thứ \(i\). Thao tác này mất \(P_i\) giây.

Chúng tôi cho rằng Emacs++ sẽ đơn giản đối với người dùng thành thạo, nhưng vẫn cần hiểu mức độ hiệu quả của nó. Ta có một chương trình Lisp++ duy nhất và danh sách \(Q\) truy vấn về chương trình đó; mỗi truy vấn gồm vị trí bắt đầu \(S_j\) và vị trí kết thúc \(E_j\). Để trả lời truy vấn thứ \(j\), bạn phải xác định khoảng thời gian nhỏ nhất có thể \(N_j\) (tính bằng giây) để đưa con trỏ từ \(S_j\) tới \(E_j\) nếu luôn đưa ra các quyết định tối ưu.

Hãy in tổng của tất cả các giá trị \(N_j\) đó.

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test \(T\). Tiếp theo là \(T\) bộ test. Dòng đầu mỗi bộ test chứa hai số nguyên \(K\), là độ dài chương trình Lisp++, và \(Q\), là số lượng truy vấn.

Dòng thứ hai chứa chuỗi \(P\) gồm \(K\) ký tự, mỗi ký tự là ( hoặc ), biểu diễn một chương trình Lisp++ (chuỗi dấu ngoặc cân bằng) như mô tả ở trên.

Dòng thứ ba, thứ tư và thứ năm, mỗi dòng chứa \(K\) số nguyên. Số thứ \(i\) trên các dòng này lần lượt là \(L_i\), \(R_i\) và \(P_i\) đã mô tả ở trên.

Dòng thứ sáu và thứ bảy, mỗi dòng chứa \(Q\) số nguyên. Số thứ \(j\) trên các dòng này lần lượt là \(S_j\) và \(E_j\) đã mô tả ở trên.

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là tổng các giá trị \(N_j\).

Ràng buộc

• \(1 \le T \le 100\).
• \(K = 10^5\) và \(Q = 10^5\) đối với nhiều nhất 9 bộ test.
• \(2 \le K \le 1000\) và \(1 \le Q \le 1000\) trong tất cả trường hợp còn lại.
• Độ dài của \(P\) bằng \(K\).
• \(P\) là chuỗi dấu ngoặc cân bằng như mô tả ở trên.
• \(1 \le S_j \le K\) với mọi \(j\).
• \(1 \le E_j \le K\) với mọi \(j\).

Phân nhóm

Test Set 1 (Visible Verdict)

• \(L_i = 1\) với mọi \(i\).
• \(R_i = 1\) với mọi \(i\).
• \(P_i = 1\) với mọi \(i\).

Test Set 2 (Hidden Verdict)

• \(1 \le L_i \le 10^6\) với mọi \(i\).
• \(1 \le R_i \le 10^6\) với mọi \(i\).
• \(1 \le P_i \le 10^6\) với mọi \(i\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

12 5
(()(((()))))
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
7 4 4 12 5
12 11 10 1 6
```
???+ success "Output"

Case #1: 10

    Thời gian ngắn nhất cho các truy vấn như sau:


    1. Di chuyển sang phải năm lần từ vị trí 7 đến 12, mất 5 giây.
    2. Dịch chuyển tức thời từ vị trí 4 đến 11, mất 1 giây.
    3. Dịch chuyển tức thời từ vị trí 4 đến 11, rồi sang trái đến 10, mất 2 giây.
    4. Dịch chuyển tức thời từ vị trí 12 đến 1, mất 1 giây.
    5. Di chuyển sang phải từ vị trí 5 đến 6, mất 1 giây.

    Vì vậy, tổng thời gian là $5+1+2+1+1=10$ giây.

Nguồn

Google Code Jam 2020, Vòng 2, bài Emacs++.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.