Câu 1. Xâu đối xứng

Một xâu kí tự được gọi là đối xứng nếu đảo ngược xâu đó thì vẫn được xâu ban đầu. Ví dụ xâu "aba" là xâu đối xứng, còn xâu "abc" hay "abca" thì không phải. Cho một xâu S chỉ gồm các kí tự latin thường ('a' → 'z') và T testcase, mỗi testcase gồm một cặp số nguyên dương (L, R).

Yêu cầu: Với mỗi testcase, nếu xâu con (S[l],S[l+1],..,S[r]) là xâu đối xứng thì in ra "YES", ngược lại in ra "NO".

Input

• Dòng đầu là một số nguyên dương N là độ dài xâu kí tự (N <= 5000)
• Dòng thứ hai chứa xâu kí tự ~S~
• Dòng thứ ba là một số nguyên dương T ~(T <= 10^6)~
• ( T ) dòng tiếp theo, mỗi dòng là một cặp số nguyên dương (L, R), dữ liệu đảm bảo 1 <= L <= R <= N

Output

• Gồm ( T ) dòng, mỗi dòng in ra YES/NO theo kết quả bài toán.

Sample Input 1

5
abcbc
4
1 3
3 5
2 5
4 4

Sample Output 1

NO
YES
NO
YES

Sample Input 1

5 3
1
2
8
4
9

Sample Output 1

3

Đề bài

Ba anh em An, Bình, Cường có ~n~ gói kẹo, gói thứ ~i~ có ~a_i~ cái kẹo. Cả ba quyết định chia ~n~ gói kẹo thành ba phần theo các nguyên tắc:

• Không bóc các gói kẹo.
• Chia các gói kẹo thành ba phần, gọi ~A \geq B \geq C~ là số kẹo tương ứng của ba phần, khi đó An sẽ nhận phần có ~A~ cái kẹo, Bình sẽ nhận phần có ~B~ cái kẹo, Cường sẽ nhận phần có ~C~ cái kẹo.

Cách chia để cả ba anh em vui nhất là cách chia có giá trị ~(A - C)~ nhỏ nhất.

Yêu cầu: Cho ~a_1, a_2, \dots, a_n~ là số kẹo của ~n~ gói, hãy tìm cách chia thỏa mãn để ~(A - C)~ đạt giá trị nhỏ nhất.

Input

• Dòng đầu chứa số nguyên ~n~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ (~a_i \leq 10^9~).

Output

• Ghi ra một dòng chứa một số là giá trị ~(A - C)~ nhỏ nhất tìm được.

Ví dụ

Sample Input 1

4
5 5 3 4

Sample Output 1

2

Giới hạn

• Thời gian: 2.0s
• Bộ nhớ: 256M

Subtasks

• Subtask 1: Có 25% số test có ~n = 3~.
• Subtask 2: Có 50% số test có ~n \leq 10~.
• Subtask 3: Có 25% số test còn lại có ~n \leq 50~ và tổng số kẹo trong ~n~ gói không vượt quá ~1000~.

Đề bài

Có ~N~ thành phố và ~M~ đường hàng không hai chiều giữa một số cặp thành phố nào đó, các đường bay được quản lý bởi ~x~ (~1 \leq x \leq 16~) hãng hàng không. Các thành phố được đánh số từ ~1~ tới ~N~ (~N \leq 100~) và các hãng được đánh số từ ~1~ tới ~x~.

Được biết chi phí bay trực tiếp giữa hai thành phố ~i, j~ bất kỳ (nếu như có đường bay) là ~C~. Nếu đang đi máy bay của một hãng đến sân bay nào đó rồi chuyển sang máy bay của hãng khác thì sẽ phải mất thêm một khoản phụ phí ~A~.

Yêu cầu: Cho trước hai thành phố ~S~ và ~F~, hãy tìm hành trình bay từ thành phố ~S~ đến thành phố ~F~ với chi phí ít nhất. Với giả thiết rằng luôn luôn tồn tại cách bay từ ~S~ tới ~F~.

Input

• Dòng 1 ghi sáu số nguyên dương ~N, M, C, A, S, F~ (~1 \leq A, C \leq 100~)
• ~M~ dòng tiếp theo, mỗi dòng có dạng ~u\ v\ k\ x_1\ x_2\ \dots\ x_k~ cho biết rằng giữa thành phố ~u~ và thành phố ~v~ có ~k~ đường bay và ~x_1, x_2, \dots, x_k~ là số hiệu các hãng sở hữu đường bay đó.

Output

• Một dòng duy nhất là chi phí tối thiểu phải trả.

Ví dụ

Sample Input 1

15 16 3 2 1 5
1 2 1 1
2 3 1 1
3 4 2 1 2
3 9 1 2
4 9 1 1
5 10 2 1 3
6 7 1 1
6 11 1 1
7 8 1 1
7 13 1 2
8 9 1 1
10 15 1 3
11 12 1 1
12 13 1 1
13 14 2 1 3
14 15 2 1 3

Sample Output 1

37

Giới hạn

• Thời gian: ~2.0s~
• Bộ nhớ: ~256M~
• ~1 \leq x \leq 16~
• ~N \leq 100~

Subtasks

• Subtask 1: Có ~25%~ số test đầu tiên các tuyến bay được quản lý bởi cùng một hãng hàng không;
• Subtask 2: Có ~25%~ số test tiếp theo các tuyến bay được bố trí dưới dạng thành phố ~i~ chỉ có ~2~ tuyến bay đến thành phố ~i - 1~ và ~i + 1~, trừ thành phố ~1~ chỉ có tuyến bay đến thành phố ~2~ và thành phố ~n~ chỉ có tuyến bay đến thành phố ~n - 1~;
• Subtask 3: Có ~50%~ số test cuối cùng không có ràng buộc gì.

Giải thích ví dụ

Với mạng lưới đường không như hình minh họa (trang 2 ): cần đi từ thành phố ~1~ đến thành phố ~5~. Chi phí đường bay trực tiếp giữa hai thành phố bất kỳ ~C = 3~, phụ phí chuyển tuyến ~A = 2~. Các số ghi bên cạnh các đường bay trực tiếp là tên các hãng sở hữu đường bay đó.