Contest giao lưu lớp 10 các trường Chuyên (Lần 6)

Quang có \(n\) khối gỗ màu đỏ, mỗi khối có kích thước \(1 \times 1 \times a\) (cm) và \(m\) khối gỗ màu xanh, mỗi khối có kích thước \(1 \times 1 \times b\) (cm). Quang xếp các khối gỗ thành một cột thẳng đứng có đáy là một hình vuông kích thước \(1 \times 1\) (cm) và tiến hành đo chiều cao của cột gỗ, ký hiệu là \(h\). Quang thử tất cả các cách xếp khác nhau và ghi lại các giá trị \(h\) thu được.

Yêu cầu: Vì số lượng giá trị \(h\) mà Quang ghi lại được là quá lớn, bạn hãy giúp Quang đếm xem có bao nhiêu giá trị \(h\) khác nhau mà Quang đã tạo ra.

Input

• Nhập từ file WOOD.inp:
  • Một dòng duy nhất gồm bốn số nguyên dương \(a, b, n, m\) (\(1 \le a, b, n, m \le 10^9\)).

Output

• Ghi ra file WOOD.out:
  • Một dòng duy nhất là số giá trị \(h\) khác nhau mà Quang tạo được. Vì số giá trị có thể rất lớn nên chỉ cần in ra phần dư của nó khi chia cho \(10^9 + 7\).

Example

2 3 1 2

5

3 3 1 1

2

Ràng buộc bổ sung

• 20% số điểm có \(n = m = 1\).
• 20% số điểm khác có \(a = b\).
• 10% số điểm khác có \(m = 1\).
• 10% số điểm khác có \(n, m \le 10\).
• 10% số điểm khác có \(n, m \le 1000\).
• 10% số điểm khác có \(b = 1\).
• 10% số điểm khác có \(m \le 10^5\).
• 10% số điểm còn lại không có giới hạn gì thêm.

Người dân thành phố SQRT đang chuẩn bị đón Tết Ất Tỵ 2025.

Năm nay, do kinh tế khó khăn, chính quyền thành phố muốn tái sử dụng những món đồ trang trí Tết từ những năm trước đó. Một trong số đó là một dãy đèn lồng với nhiều màu sắc rực rỡ.

Dãy đèn lồng gồm \(n\) chiếc được đánh số từ \(1\) đến \(n\). Chiếc đèn thứ \(i\) có màu \(a_i\). Chính quyền muốn chọn ra một đoạn gồm ít nhất \(k\) chiếc đèn liên tiếp trong dãy để sử dụng trong năm mới, và thay thế một số chiếc đèn trong đoạn này sang một màu khác sao cho sau khi thay thế thì đoạn gồm tối đa \(x\) màu khác nhau. Chi phí để thay thế một chiếc đèn sang màu khác là \(1\) đồng.

Chính quyền muốn thử nghiệm \(q\) phương án, mỗi phương án là một cặp số \((k, x)\) khác nhau. Với mỗi phương án, họ cần tính toán chi phí tối thiểu để có thể tạo ra đoạn đèn trang trí thỏa mãn yêu cầu.

Yêu cầu

Là một lập trình viên chuyên thực hiện những nhiệm vụ tính toán cho chính quyền thành phố, bạn hãy viết một chương trình giải quyết phương án thử nghiệm trên trong thời gian ngắn nhất.

Input

• Dòng đầu tiên gồm ba số nguyên dương \(n, q, c\) (\(1 \le c \le n \le 10^5\), \(1 \le q \le 400\)).
• Dòng tiếp theo gồm \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le c\)).
• \(q\) dòng tiếp theo, mỗi dòng gồm hai số nguyên dương \(k, x\) (\(1 \le k \le n\), \(1 \le x \le c\)).

Output

• Với mỗi phương án thử nghiệm, in ra chi phí nhỏ nhất tìm được trên một dòng.

Ràng buộc bổ sung

• \(20\%\) số điểm có \(n \le 200\) và \(c = 2\).
• \(20\%\) số điểm khác có \(c = 2\).
• \(20\%\) số điểm khác có \(x = 1\) trong mọi phương án.
• \(10\%\) số điểm khác có \(q = 1\).
• \(10\%\) số điểm khác có \(k\) giống nhau trong mọi phương án.
• \(10\%\) số điểm khác có \(q \le 30\).
• \(10\%\) số điểm còn lại không có giới hạn gì thêm.

Example

5 2 3
1 2 1 2 3
5 2
3 1

1
1

Hà có một dãy số nguyên \(a_1, a_2, \dots, a_n\). Cô muốn tìm một đoạn con liên tiếp (có thể không chứa phần tử nào) của dãy mà có tổng lớn nhất.

Nhắc lại, một dãy \(b\) được gọi là đoạn con liên tiếp của \(a\) khi và chỉ khi có thể thu được \(b\) từ \(a\) bằng cách xóa đi một số phần tử đầu tiên và cuối cùng của dãy \(a\). Ví dụ, 2, 3, 4 và 1, 2, 3 là các đoạn con của 1, 2, 3, 4, 5, trong khi 1, 3, 4 thì không.

Sau khi tìm được dãy con thỏa mãn, Hà thấy dãy vừa rồi có tổng không đủ lớn nên cô quyết định tạo thêm một dãy số \(m_1, m_2, \dots, m_k\). Với mỗi giá trị \(m_i\), cô có thể chọn tối đa một đoạn con liên tiếp của \(a\) và nhân giá trị các phần tử trong đoạn với \(m_i\). Sau khi thực hiện thao tác với toàn bộ dãy \(m\), Hà sẽ tìm đoạn con có tổng lớn nhất của dãy và tính tổng các phần tử trong đoạn con này.

Do số cách thực hiện thao tác là quá lớn, Hà đã nhờ Vũ tìm cách thực hiện sao cho kết quả cuối cùng thu được là lớn nhất. Vũ cũng cảm thấy bài toán này quá khó nên anh cần các bạn giúp anh giải quyết nó.

Yêu cầu: Hãy giúp Vũ tìm một cách thực hiện các thao tác nhân sao cho tổng cuối cùng thu được là lớn nhất.

Input

• Dòng đầu tiên gồm hai số nguyên dương \(n, k\) (\(1 \le n \le 10^5, 1 \le k \le 6\)).
• Dòng tiếp theo gồm \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(|a_i| \le 1000\)).
• Dòng tiếp theo gồm \(k\) số nguyên \(m_1, m_2, \dots, m_k\) (\(|m_i| \le 50\)).

Output

• Dòng đầu tiên là tổng cuối cùng tối đa tìm được.
• \(k\) dòng tiếp theo, dòng thứ \(i\) gồm hai số nguyên \(u_i, v_i\) mô tả thao tác của Hà đối với số \(m_i\):
  • Nếu \(u_i = v_i = 0\), Hà sẽ bỏ qua số \(m_i\).
  • Ngược lại, Hà sẽ nhân các số trong đoạn \([u_i, v_i]\) lên \(m_i\). Hiển nhiên điều kiện hợp lệ là \(1 \le u_i \le v_i \le n\).
• Dòng cuối cùng gồm hai số nguyên dương \(l, r\) – Hà sẽ tính tổng các số trong đoạn \([l, r]\). Nếu chọn đoạn rỗng, \(l = r = 0\).
• Nếu có nhiều cách thực hiện thao tác cùng cho ra kết quả tối ưu, in ra một cách bất kỳ.

Ràng buộc bổ sung

• 20% số điểm có \(n \le 300\) và \(k = 1\).
• 20% số điểm khác có \(k = 1\).
• 15% số điểm khác có \(m_i > 0\) với mọi \(i\).
• 15% số điểm khác có \(m_1 = m_2 = \dots = m_k\).
• 10% số điểm khác có \(k \le 3\).
• 10% số điểm khác có \(k \le 4\).
• 10% số điểm còn lại không có giới hạn gì thêm.

Example

5 3
1 2 3 -4 -5
-1 -3 4

180
1 3
1 5
1 5
1 5