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.

Bạn được cung cấp một chuỗi mật mã S có độ dài N. Chuỗi này chỉ chứa K loại chữ cái viết hoa đầu tiên trong bảng chữ cái tiếng Anh (ví dụ: nếu K = 3, chuỗi sẽ chỉ chứa 3 loại chữ cái là A, B và C).

Từ chuỗi S ban đầu, bạn có thể rút trích ra một "chuỗi con" bằng cách chọn ra một số chữ cái và giữ nguyên thứ tự ban đầu của chúng (nói cách khác, bạn được quyền xóa bớt một số chữ cái bị thừa). Ví dụ: Với chuỗi gốc là "ABCDE", bạn có thể tạo ra chuỗi con "ADE" hoặc "BD", nhưng không thể tạo ra chuỗi "DEA" vì nó bị ngược thứ tự.

Một chuỗi con được gọi là "Đội Hình Cân Bằng" nếu số lượng của TẤT CẢ K loại chữ cái trong chuỗi đó là HOÀN TOÀN BẰNG NHAU.

Nhiệm vụ của bạn: Hãy tìm cách xóa bớt ký tự sao cho phần còn lại tạo thành một "Đội Hình Cân Bằng" dài nhất có thể. In ra độ dài lớn nhất đó.

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

• Dòng 1: Chứa hai số nguyên N (1 <= N <= 10^5) là độ dài của chuỗi S, và K (1 <= K <= 26) là số loại chữ cái.

• Dòng 2: Chứa chuỗi S có độ dài N (chỉ gồm K loại chữ cái viết hoa đầu tiên).

Dữ liệu ra (Output):

• In ra một số nguyên duy nhất là độ dài của "Đội Hình Cân Bằng" dài nhất tìm được.

Ví dụ:

Input:

9 3 
ACAABCCAB

Output:

6

Hệ thống quản lý hiện tại đang ở phiên bản X. Quản trị viên cần nâng cấp lên phiên bản Y. Bảng điều khiển bị lỗi, chỉ còn đúng 2 nút bấm với chức năng:

Nhân đôi số phiên bản hiện tại (A = A * 2).

Giảm số phiên bản hiện tại đi 1 (A = A - 1).

Hãy tính số lần bấm nút ít nhất để từ phiên bản X đạt được đúng phiên bản Y.

Dữ liệu vào: Hai số nguyên X và Y (1 <= X, Y <= 10^9).

Kết quả ra: Số lần bấm nút ít nhất.

Ví dụ:

Input:

2 3

Output:

2

(Bấm nhân 2: 2->4, bấm trừ 1: 4->3).

Input:

5 8

Output:

2

(Bấm trừ 1: 5->4, bấm nhân 2: 4->8).

Cho một xâu ký tự S. Bạn được yêu cầu cắt xâu S thành các đoạn con sao cho mỗi đoạn con đều là một xâu đối xứng (Palindrome). Tuy nhiên, mỗi nhát cắt đều tiêu tốn năng lượng. Hãy tìm số lần cắt ít nhất để toàn bộ các đoạn con đều là xâu đối xứng.

Input: Một dòng chứa xâu S chỉ gồm chữ cái in thường (Độ dài <= 2000).

Output: Số nhát cắt ít nhất.

Ví dụ:

Input:

ababbbabbababa

Output:

3

(Giải thích: Cắt thành a | babbbab | b | ababa. Tổng cộng 3 nhát cắt).

Có N bộ quần áo ướt, bộ thứ i chứa A_i lượng nước. Nếu để khô tự nhiên, mỗi phút mỗi bộ giảm 1 lượng nước. Bạn có một chiếc máy sấy, mỗi phút chỉ sấy được 1 bộ quần áo. Khi dùng máy sấy, bộ quần áo đó sẽ giảm K lượng nước trong phút đó (các bộ khác vẫn khô tự nhiên giảm 1). Hãy tính thời gian (số phút) ít nhất để tất cả quần áo đều khô hoàn toàn (lượng nước <= 0).

Input:

Dòng 1: Hai số nguyên N, K (1 <= N <= 10^5, 1 <= K <= 10^9).

Dòng 2: N số nguyên Ai (1 <= Ai <= 10^9).

Output: Số phút ít nhất cần thiết.

Ví dụ:

Input:

3 5
2 3 9

Output:

3

(Giải thích: Phút 1: sấy áo 3 (còn 4), áo 1,2 khô tự nhiên (còn 1,2). Phút 2: sấy áo 3 (còn -1), áo 1,2 tự nhiên (còn 0,1). Phút 3: sấy áo 2 (còn -4), áo 1 (đã khô). Tổng 3 phút).

Trên bàn cờ kích thước N x M, một quân Mã xuất phát tại ô (1, 1) và cần đi đến ô (N, M). Do quân Mã này bị thương nên nó chỉ có thể di chuyển theo hướng tiến lên: Từ ô (i, j) chỉ được nhảy đến ô (i+1, j+2) hoặc (i+2, j+1). Có một số ô bị đặt bẫy không thể nhảy vào. Hãy đếm số cách để quân Mã đến được đích (kết quả chia dư cho 10^9+7).

Input:

Dòng 1: N, M, K (1 <= N, M <= 1000, 0 <= K <= 10^4). (K là số lượng bẫy).

K dòng tiếp theo: Mỗi dòng tọa độ x, y của bẫy.

Output: Số cách di chuyển modulo 10^9+7.

Ví dụ:

Input 01:

4 4 0

Output 01:

2

(Giải thích: Cách 1: (1,1) -> (2,3) -> (4,4). Cách 2: (1,1) -> (3,2) -> (4,4)).

Input 02:

4 4 1
2 3

Output 02:

1