Bình mua bán cổ phiếu HCN trên thị trường chứng khoán. Giả sử giá của một cổ phiếu HCN trong vòng N ngày lần lượt là A1, A2,..., AN. Biết rằng mỗi ngày Bình chỉ thực hiện một trong những hoạt động sau:

1. Mua một cổ phiếu HCN;

2. Bán số lượng cổ phiếu HCN bất kì mà Bình đang sở hữu;

3. Không thực hiện bất kì giao dịch nào.

Yêu cầu: Bình thực hiện mua bán cổ phiếu HCN như thế nào để thu được lợi nhuận lớn nhất nếu anh ấy tham gia mua bán bắt đầu từ ngày thứ T cho trước?

Dữ liệu nhập vào:

• Dòng đầu tiên gồm số nguyên dương N (N ≤ 10^5) là số ngày biết giá cổ phiếu;

• Dòng thứ hai gồm N số nguyên dương A1, A2, ..., Av tương ứng là giá của một cổ phiếu VNI trong từng ngày (Ai ≤ 10^9; 1 ≤ i ≤ N);

• Dòng thứ ba gồm một số nguyên dương Q là số lượng truy vấn (Q ≤ 10^5);

Q dòng sau, mỗi dòng gồm một số nguyên dương T (T < N) thể hiện cho ngày đầu tiên mà Bình tham gia việc mua bán cổ phiếu HCN.

Kết quả ghi ra:

Q dòng, mỗi dòng gồm một số nguyên duy nhất là lợi nhuận lớn nhất mà Bình thu được ở mỗi truy vấn tương ứng.

Ràng buộc:

• Có 50% số test tương ứng với 50% số điểm thoa mãn: N ≤ 1000; Q = 1;

• 30% số test khác tương ứng với 30% số điểm thỏả mãn N ≤ 10^5; Q = 1;

• 20% số test còn lại tương ứng với 20% số điểm không có rằng buộc gì thêm.

Ví dụ:

Input:

4
1 2 5 4
2
1
3

Otuput:

7
0

Giải thích:

• Bình bắt đầu tham gia mua bán HCN vào ngày 1:

• Ngày 1: mua 1 HCN với giá là 1.

• Ngày 2: mua 1 HCN với giá là 2.

• Ngày 3: bán 2 HCN với giá là 5.

• Ngày 4: không mua hay bán HCN vào ngày này.

→ Lợi nhuận thu được là: - 1 - 2 + 2 × 5 = 7.

• Bình bắt đầu tham gia mua bán HCN vào ngày 3:

• Bình không mua bán HCN vào ngày 3 và ngày 4.

→ Lợi nhuận thu được là: 0.

Alice có một chuỗi s. Cô ấy thực sự thích chữ "a". Cô gọi một chuỗi là tốt nếu hơn một nửa số ký tự trong chuỗi đó là "a". Ví dụ: "aaabb", "axaa" là các chuỗi tốt và "baca", "awwwa", "" (chuỗi trống) thì không. Alice có thể xóa một số ký tự khỏi chuỗi s của mình. Cô ấy muốn biết chuỗi dài nhất còn lại là gì sau khi xóa một số ký tự (có thể bằng 0) để có được chuỗi được coi là tốt. Nó được đảm bảo rằng chuỗi có ít nhất một "a" trong đó, vì vậy câu trả lời luôn tồn tại.

Đầu vào: Nhập vào một chuỗi s (1≤ | s |<= 50) bao gồm các chữ cái tiếng Anh viết thường. Nó được đảm bảo rằng có ít nhất một "a" trong s.

Đầu ra: In một số nguyên duy nhất, độ dài của chuỗi tốt nhất dài nhất mà Alice có thể nhận được sau khi xóa một số ký tự khỏi s.

Input:

xaxxxxa

Output:

3

Tại lễ hội đền Hakurei năm nay có N gian hàng bán đồ ăn được xếp thành một hàng ngang và đánh số thứ tự từ 1 đến N. Ban tổ chức bán ra Q loại "Vé Combo". Mỗi "Vé Combo" thứ i sẽ cho phép thực khách ăn một mạch tất cả các gian hàng từ vị trí Bi đến vị trí Ri.

Vì quá đói, cô nàng Yuyuko quyết định đi càn quét lễ hội M lần. Trong lần đi ăn thứ j, cô nàng chơi lớn bằng cách mua và sử dụng tất cả các "Vé Combo" từ loại Xj đến loại Yj.

Nhiệm vụ của bạn: Hãy tính toán xem sau M lần đi càn quét đó, Yuyuko đã ghé thăm mỗi gian hàng tổng cộng bao nhiêu lần?

Dữ liệu vào (Input):

• Dòng 1: Gồm 3 số nguyên dương N, Q, M (tương ứng với số lượng gian hàng, số lượng loại Vé Combo, và số lần đi ăn).

• Q dòng tiếp theo: Mỗi dòng chứa 2 số nguyên Bi và Ri (1 <= Bi <= Ri <= N), thể hiện phạm vi gian hàng của Vé Combo thứ i.

• M dòng tiếp theo: Mỗi dòng chứa 2 số nguyên Xj và Yj (1 <= Xj <= Yj <= Q), thể hiện dải Vé Combo mà Yuyuko đã gọi trong lần đi ăn thứ j.

Dữ liệu ra (Output):

• In ra một dòng duy nhất gồm N số nguyên không âm, cách nhau bởi khoảng trắng. Số nguyên thứ k thể hiện tổng số lần Yuyuko đã ghé thăm gian hàng thứ k.

Ràng buộc (Subtasks):

• 40% số điểm: N, Q, M <= 100.

• 30% số điểm: N, Q, M <= 5000.

• 30% số điểm: N, Q, M <= 10^5.

Ví dụ:

Input:

3 3 3 
1 2 
2 3 
1 3 
2 3 
1 2 
1 3

Output:

4 7 5

Giải thích ví dụ: Lễ hội có 3 gian hàng, 3 loại Vé Combo, và Yuyuko đi ăn 3 lần.

• Danh sách 3 loại Vé Combo:

• Combo 1: Ăn từ gian 1 đến gian 2.

• Combo 2: Ăn từ gian 2 đến gian 3.

• Combo 3: Ăn từ gian 1 đến gian 3.

• Quá trình đi ăn của Yuyuko:

• Lần 1 (Input là 2 3): Dùng Combo 2 và Combo 3. (Ghé gian 2, 3 và gian 1, 2, 3).

• Lần 2 (Input là 1 2): Dùng Combo 1 và Combo 2. (Ghé gian 1, 2 và gian 2, 3).

• Lần 3 (Input là 1 3): Dùng Combo 1, 2, và 3. (Ghé gian 1, 2; gian 2, 3 và gian 1, 2, 3).

• Tổng kết:

• Gian 1 được ghé 4 lần.

• Gian 2 được ghé 7 lần.

• Gian 3 được ghé 5 lần.

Keanu Reeves đang mắc kẹt trong thế giới ảo Ma Trận. Để chứng minh mình đang ở trong thế giới ảo, anh cần giải quyết một bài toán với chuỗi mật mã chỉ gồm các chữ số 0 và 1.

Trong thế giới này, một chuỗi mật mã được gọi là "Chuỗi An Toàn" nếu số lượng chữ số 0 và số lượng chữ số 1 trong chuỗi đó KHÁC NHAU. Ví dụ: Các chuỗi 1, 101, 0000 là an toàn. Các chuỗi 01, 1001, 111000 không an toàn (vì số lượng chữ số 0 bằng với số lượng chữ số 1).

Nhiệm vụ của bạn: Bạn được cấp một chuỗi mật mã S ban đầu. Bạn hãy cắt chuỗi S này thành ÍT ĐOẠN NHẤT có thể, sao cho TẤT CẢ các đoạn sau khi cắt đều là "Chuỗi An Toàn".

Lưu ý:

• Nếu chuỗi S ban đầu đã an toàn sẵn, bạn không cần cắt (tức là số đoạn cắt được k = 1).

• Nếu có nhiều cách cắt tạo ra số đoạn tối thiểu giống nhau, bạn có thể in ra bất kỳ cách nào.

Dữ liệu vào (Input):

• Dòng 1: Chứa một số nguyên N (1 <= N <= 100) là độ dài của chuỗi S.

• Dòng 2: Chứa chuỗi S có độ dài N (chỉ gồm các ký tự 0 và 1).

Dữ liệu ra (Output):

• Dòng 1: In ra số nguyên K là số lượng đoạn ít nhất mà bạn cắt được.

• Dòng 2: In ra K đoạn mật mã đó, mỗi đoạn cách nhau một khoảng trắng (dấu cách).

Ví dụ:

Input:

6 
100011

Output:

2 
100 011

Giải thích ví dụ: Chuỗi 100011 có 3 số '0' và 3 số '1' (không an toàn). Ta cắt thành 2 đoạn là 100 (có 2 số '0', 1 số '1') và 011 (có 1 số '0', 2 số '1'). Cả 2 đoạn này đều an toàn và đây là cách cắt tạo ra ít đoạn nhất.