Bài tập

Hệ thống có sẵn một danh sách tên tài khoản. Có \(N\) người lần lượt xin đăng ký các tên mới. Với mỗi người, hãy cho biết tên xin đăng ký có bị trùng với danh sách sẵn có hay không (mỗi yêu cầu được kiểm tra độc lập với danh sách ban đầu, so sánh phân biệt chữ hoa và chữ thường).

Input

• Dòng đầu chứa danh sách các tài khoản đã có, cách nhau bởi dấu cách (ít nhất một tài khoản).
• Dòng thứ hai chứa số nguyên dương \(N\).
• \(N\) dòng tiếp theo, mỗi dòng là một tên tài khoản cần đăng ký.

Output

Với mỗi yêu cầu in trên một dòng CO nếu đăng ký được (tên chưa tồn tại) hoặc KHONG nếu tên đã tồn tại.

Constraints

• Mỗi tên gồm chữ cái và chữ số, độ dài không quá \(20\).
• Danh sách có không quá \(10^5\) tài khoản.
• \(1 \le N \le 10^5\)

Sample Input

luna9 mikan tora5 sora
4
kuma
mikan
sora
luna9

Sample Output

CO
KHONG
KHONG
KHONG

Cho hai xâu ký tự \(A\) và \(B\). Trên xâu \(A\) được phép thực hiện các phép biến đổi sau, mỗi phép tính là một thao tác:

• Xoá một ký tự bất kỳ của \(A\);
• Chèn một ký tự bất kỳ vào một vị trí bất kỳ của \(A\);
• Thay một ký tự của \(A\) bằng một ký tự khác.

Hãy tính số thao tác ít nhất để biến \(A\) thành \(B\).

Input

• Dòng đầu chứa số nguyên \(T\) là số bộ test.
• Mỗi bộ test gồm hai dòng: dòng đầu là xâu \(A\), dòng thứ hai là xâu \(B\).

Output

Với mỗi bộ test in ra một dòng là số thao tác tối thiểu.

Constraints

• \(1 \le T \le 10\)
• Mỗi xâu chỉ gồm chữ cái in hoa, độ dài từ \(1\) đến \(2000\).

Sample Input

3
KITTEN
SITTING
ABC
ABC
AAAA
B

Sample Output

3
0
4

Explanation

KITTEN \(\to\) SITTEN (thay K bằng S) \(\to\) SITTIN (thay E bằng I) \(\to\) SITTING (chèn G): 3 thao tác. Bộ test thứ hai hai xâu giống nhau. Bộ test thứ ba: giữ lại một chữ A, thay bằng B rồi xoá 3 chữ còn lại, tổng 4 thao tác.

Hai chú kangaroo đứng trên một đường thẳng và nhảy cùng chiều (về phía số lớn hơn), các lần nhảy của hai chú diễn ra đồng thời.

• Chú thứ nhất xuất phát ở vị trí \(x_1\), mỗi lần nhảy tiến thêm \(v_1\).
• Chú thứ hai xuất phát ở vị trí \(x_2\), mỗi lần nhảy tiến thêm \(v_2\).

Hỏi có tồn tại một số lần nhảy \(t \ge 0\) (sau đúng \(t\) lần nhảy của mỗi chú) mà hai chú đứng cùng một vị trí hay không? In YES nếu có, ngược lại in NO.

Input

Một dòng gồm bốn số nguyên \(x_1, v_1, x_2, v_2\).

Output

In YES hoặc NO.

Constraints

• \(0 \le x_1 \le x_2 \le 10000\).
• \(1 \le v_1, v_2 \le 10000\).

Sample Input

2 5 11 2

Sample Output

YES

Explanation

Sau \(3\) lần nhảy: chú thứ nhất ở \(2 + 3 \cdot 5 = 17\), chú thứ hai ở \(11 + 3 \cdot 2 = 17\).

Cho một xâu ký tự \(S\) đã được chuẩn hóa: chỉ gồm các chữ cái tiếng Anh viết thường và dấu cách; giữa hai từ liên tiếp có đúng một dấu cách; không có dấu cách ở đầu và cuối xâu.

Hãy biến đổi xâu bằng cách viết hoa chữ cái đầu tiên của mỗi từ (các chữ cái còn lại giữ nguyên) rồi in kết quả.

Gợi ý: xây dựng hàm \(HoadauTu(S)\) thực hiện việc này.

Input

• Một dòng duy nhất chứa xâu \(S\).

Output

• In ra xâu \(S\) sau khi viết hoa chữ cái đầu mỗi từ.

Constraints

• \(1 \le |S| \le 10^6\)

Sample Input 1

nguyen van an

Sample Output 1

Nguyen Van An

Sample Input 2

hanoi

Sample Output 2

Hanoi