Cho xâu \(s\) gồm các kí tự latin (có cả chữ hoa lẫn chữ thường). Nhiệm vụ của bạn là chuyển hoá xâu \(s\) thành \(s'\) theo quy tắc sau:

• Mỗi kí tự nguyên âm trong xâu \(s\) khi chuyển sang \(s'\) đều phải là chữ hoa.

• Mỗi kí tự phụ âm trong xâu \(s\) khi chuyển sang \(s'\) đều phải là chữ thường.

(Ghi chú: Nguyên âm bao gồm những kí tự: \(\left\{u,e,o,a,i\right\}\))

Input

• Dòng thứ nhất chứa số \(t(1\le t\le 100)\) - Thể hiện số testcase

• \(t\) dòng tiếp theo, mỗi dòng chứa một xâu \(s\) (biết rằng xâu \(s\) chứa không quá \(100\) ký tự)

Output

• In ra đáp án cần tìm

Example

4
oikmOP
OOOOk
kkkaAA
ccMMA

OIkmOp
OOOOk
kkkAAA
ccmmA

Một xâu được gọi là cân bằng nếu nó thỏa mãn các điều kiện:

• Có độ dài \(n\) là một số nguyên dương chẵn.
• Mọi ký tự xuất hiện ở nửa bên trái (từ vị trí \(1\) đến vị trí \(\dfrac{n}{2}\)) cũng đều xuất hiện ở nửa bên phải (từ vị trí \(\dfrac{n}{2}+1\) đến \(n\)).
• Mọi ký tự xuất hiện ở nửa bên phải cũng đều xuất hiện ở nửa bên trái.

(Lưu ý rằng ta đánh chỉ số cho các ký tự từ \(1\) đến \(n\)).

Cho xâu \(s\) dài không quá \(10^5\) ký tự, hãy lập trình kiểm tra xem nó có phải xâu cân bằng hay không.

Input

• Dòng đầu chứa số nguyên dương \(T\) \((T\leq 10)\) là số lượng câu hỏi.

• Mỗi dòng trong \(T\) dòng tiếp theo chứa một xâu \(s\) gồm không quá \(10^5\) chữ cái tiếng Anh in thường.

Output

• In ra \(T\) dòng, mỗi dòng ghi YES nếu xâu tương ứng trong input là một xâu cân bằng, hoặc NO trong trường hợp ngược lại.

Example

4
baohieplpvip
abccba
anna
lqdoj

NO
YES
YES
NO

Chắc hẳn các bạn đã quá quen với cách tính tổng các dãy số như \(1+2+3+\dots+n\) hay \(1-2+3-4+5-\dots+n\).

Hãy tính tổng \(A = -1^2+2^2-3^2+4^2-5^2+\dots\) gồm \(n\) số hạng. Nói cách khác, hãy tính biểu thức sau:

Input

• Dòng đầu tiên gồm 1 số \(t\), là số lượng câu hỏi
• \(t\) dòng tiếp theo, dòng thứ \(i\) gồm số \(n\).

Output

In ra \(t\) dòng, dòng thứ \(i\) là đáp án của bài toán tại câu hỏi thứ \(i\).

Example

2
6
9

21
-45

Subtask

• 50% số test: \(n \le 10^6\)
• 50% số test: \(n \le 10^9\)

ami ?có một dãy số nguyên \(a\) gồm \(N\) phần tử và một số \(k\). Các bạn được làm thao tác sau không quá \(m\) lần:

• Chọn một cặp số \((i , j)\) thoả điều kiện \(1 ≤ i, j ≤ N\) và \(a[i] ≥ k\). Sau đó, gán \(a[i] = a[i] - k\) và \(a[j] = a[j] + k\).

Hãy tìm cách tận dụng thao tác trên để sau khi chuyển đổi, giá trị \(max(a[1] , a[2] , ... , a[N]) - min(a[1] , a[2] , ... , a[N])\) là nhỏ nhất có thể.

Input

• Dòng đầu tiên chứa một số nguyên dương \(k\).
• Dòng thứ hai chứa một số nguyên dương \(m\).
• Dòng tiếp theo chứa một số nguyên dương \(N\).
• \(N\) dòng tiếp theo, mỗi dòng chứa một phần tử của \(a\).

Output

• \(1\) số nguyên dương là kết quả bài toán. Giá trị nhỏ nhất của \(max(a[1] , a[2] , ... , a[N]) - min(a[1] , a[2] , ... , a[N])\).

Example

2
1
3
2
2
3

1

1
1
3
2
3
4

0

Scoring

• Subtask \(1\): \(70\)% test có \(N\), \(m\) \(\leq 50\) và 1 ≤ \(k\) , \(a[i]\) ≤ \(10^9\).
• Subtask \(2\): \(30\)% test có \(N\), \(m\) \(\leq 5 * 10^4\) và 1 ≤ \(k\) , \(a[i]\) ≤ \(10^9\).

Cho \(n\) tập hợp \(A_1,A_2,...,A_n\) biết rằng, tất cả các phần tử trong mỗi tập hợp đã cho đều thuộc đoạn \([1;m]\) và các phần tử trong mỗi tập hợp đều khác nhau từng đôi một !

Yêu cầu: Hỏi ta có thể tạo thành được bao nhiêu tập hợp khác nhau bằng cách lấy một vài tập hợp từ \(n\) tập hợp đã cho hợp lại với nhau.

Input

• Dòng thứ nhất chứa số \(t(1\le t\le 50)\) - Thể hiện số testcase

• \(t\) block tiếp theo, mỗi block có dạng như sau:

  • Dòng thứ nhất chứa hai số nguyên \(n,m(1\le n\le 100,1\le m\le 14)\)

  • \(n\) dòng tiếp theo, mỗi dòng gồm \(k+1(k\le m)\) số nguyên trong đó: Phần tử đầu tiên thể hiện số lượng phần tử của tập hợp \(A_i\) và \(k\) phần tử tiếp theo - thể hiện các phần tử của tập \(A_i\)

Output

• Ứng với mỗi testcase, in ra đáp án cần tìm.

Example

2
2 3
1 1
2 1 3
2 4
2 2 3
2 1 4

2
3

ami có một dãy số \(A\) gồm \(n\) phần tử. Với một dãy số \(B\), định nghĩa hàm \(F(B)\) chính là số phần tử riêng biệt xuất hiện trong \(B\). Hãy tính tổng \(F(B)\) với \(B\) là một dãy con liên tiếp của \(A\).

Nói cách khác, hãy tính tổng \(F([A_l, ..., A_r])\) với mọi cặp \(1 \leq l \leq r \leq n\).

Ví dụ, \(A = [1, 1, 2]\), ta sẽ có:

• \(F([1]) = F([1]) = F([2]) = F([1, 1]) = 1\)
• \(F([1, 1, 2]) = F([1, 2]) = 2\).

Tổng tất cả các hàm \(F\) sẽ là \(1 * 4 + 2 * 2 = 8\)

Nhiệm vụ của các bạn sẽ khó khăn hơn chút đỉnh. Bây giờ, dãy số sẽ được ami thay đổi \(q\) lần. Mỗi lần, ami sẽ gán \(a[i] = x\). Sau mỗi thay đổi như vậy, các bạn hãy tính tổng \(F\) của dãy số \(A\) mới.

Input

• Dòng đầu tiên chứa 1 số nguyên dương \(n\) là độ dài dãy \(A\).

• Dòng tiếp theo chứa \(n\) số nguyên dương biểu thị dãy \(A\).

• Dòng tiếp theo chứa 1 số nguyên dương \(q\) là số truy vấn.

• \(q\) dòng tiếp theo, mỗi dòng chứa một cặp số nguyên dương \(i\) \(x\) biểu thị một phép gán a[i] = \(x\).

Output

• \(q\) dòng, mỗi dòng là một số nguyên dương tương ứng với tổng \(F\) của dãy \(A\) sau khi thực hiện các biến đổi.

Scoring

Trong tất cả các test , \(1 \le i \le N\).

• Subtask \(1\) (\(50\%\) số điểm): \(N \leq 1000\), \(x \le 20, a[i] \le 20\) và \(q = 1\).

• Subtask \(2\) (\(20\%\) số điểm): \(N \leq 10^{5}\), \(x \le 20\), \(a[i] \le 20\) và \(q = 1\).

• Subtask \(3\) (\(30\%\) số điểm): \(N \leq 10^{5}\), \(x \le 10^5, a[i] \le 10^5\) và \(q \le 10^5\).

Example

4
1 2 3 4
3
1 1
2 1
3 1

20
17
13

Sau khi thua cược nặng nề ở mùa Euro và quán bánh tráng trộn của NTHA, bồ của anh ta, thua lỗ nặng nề, zipdang04 đã không còn giàu có như trước nữa, giờ anh ta chỉ ở một ngôi nhà nhỏ và còn lại rất ít tiền để tiêu xài. Nhưng vì đang còn trong tuổi trai tráng, anh ta quyết định ra đi kiếm tiền để nuôi sống bản thân và ny của mình. Thương hoàn cảnh của anh ta, một ngày nọ có một vị tiên nhân xuất hiện và cho zipdang04 một kho báu có rất nhiều của cải quý giá. Vì muốn giàu nhanh nên anh ta đã lên đường đi đến nơi chôn giậu kho báu và định mang nó về. Nhưng khi đến nơi zipdang04 mới phát hiện ra kho báu bị khoá bởi 1 ổ khoá siêu hiện đại, và muốn mở nó thì phải biết dược mật khẩu của nó, nhưng vị tiên nhân kia quên nói cho anh ta.

Mật khẩu của kho báu là mỗi dãy số bao gồm các số từ \(1\) đến \(n\) và chưa biết trước độ dài, nên zipdang04 nghĩ rằng mình phải thử rất nhiều trường hợp mới mở được kho báu. Nhưng khi nhìn sang bên cạnh, anh ta thấy một bản đồ cho biết một số rằng buộc của mật khẩu. Bản đồ chứa \(m\) cặp số \((u, v)\). Một mật khẩu hợp lệ nếu mọi cặp kề nhau trong mật khẩu đều thuộc \(m\) cặp số trong bản đồ (có thứ tự).

Ví dụ: Nếu \(n = 3\) và bản đồ chứa các cặp \((1, 2), (2, 3)\) thì:

• \([1], [2], [3], [1, 2], [2, 3]\) là các mật khẩu hợp lệ
• \([1, 2, 3]\) hợp lệ vì \((1, 2)\) và \((2, 3)\) đều có trong bản đồ
• \([1, 3, 2]\) không hợp lệ vì cặp \((1, 3)\) không có trong bản đồ
• \([3, 2]\) không hợp lệ vì \((3, 2)\) không có trong bản đồ

Nhưng đời đâu như mơ, lúc nhập mật khẩu, khi nhấn nút \(i\) anh ta phải trả \(a_i\) đồng để có thể nhấn được nút đấy, zipdang04 tự hỏi rằng trong trường hợp tệ nhất anh ta có thể mở được kho báu không. Bạn hãy tính giúp anh ấy số tiền trong trường hợp tệ nhất anh ấy phải bỏ ra nhé, vì con số này quá lớn nên hãy đưa ra mod \(10^9 + 7\). Trường hợp tệ nhất là khi zipdang04 phải thử tất cả mật khẩu có thể. Nếu số lượng mật khẩu là vô hạn thì bạn hãy đưa ra \(-1\)

Input

• Dòng đầu tiên là hai số \(n\) và \(m\) là số nút bấm và số cặp số.

• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, ..., a_n\), \(a_i\) là số tiền phải trả khi bấm nút thứ \(i\)

• \(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\), \(v\) miêu tả một cặp số trong bản đồ.

Output

• Gồm một số nguyên duy nhất là kết quả của bài toán

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(n \leq 1000, m \leq 3000\)
• Subtask \(2\) (\(60\%\) số điểm): không có điều kiện gì thêm

Example

3 3
1 2 3
1 2
2 3
1 3

24

+ $[1], [2], [3]$: tổng tiền là $1+2+3=6$
+ $[1, 2], [2, 3], [1, 3]$: tổng tiền là $12$
+ $[1, 2, 3]$: số tiền là $6$.
Như vậy tổng số tiền cần dùng là $6 + 12 + 6 = 24$.

3 2
10 20 30
1 2
2 3

200