USACO 2022 - US Open - Hạng Bạc

\(N\) người bạn của Bessie \((2\leq N \leq 10^5)\) đều sở hữu trang trại của riêng mình. Với mỗi \(1\leq i\leq N\), con bò \(𝑖\) muốn đến thăm con bò \(a_i (a_i≠i)\).

Cho một hoán vị \((p_1,p_2,…,p_N)\) của \(1 … 𝑁\), các lượt thăm diễn ra như sau.

Đối với mỗi \(i\) từ \(1\) đến \(N\):

• Nếu con bò \(a_{p_i}\) đã rời khỏi trang trại của mình thì con bò \(p_i\) vẫn ở lại trang trại của mình.
• Nếu không, con bò \(p_i\) sẽ rời trang trại của mình để đến thăm trang trại của con bò \(a_{p_i}\). Lần ghé thăm này khiến tiếng "moo" vui vẻ được kêu lên \(v_{p_i}\) lần \((0 \leq v_{p_i}\leq 10^9)\).

Tính số lượng moos tối đa có thể có sau tất cả các lượt thăm nếu chọn hoán vị \(p\) hợp lý.

Input

• Dòng đầu tiên chứa số \(N\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên cách nhau bằng dấu cách \(a_i\) và \(v_i\).

Output

Kết quả bài toán.

Scoring

• Subtask \(1\): \(a_i \ne a_j\) với mọi \(i \ne j\).
• Subtask \(2\): \(N \leq 10^3\)
• Subtask \(3\): Không có điều kiện gì thêm.

Example

4
2 10
3 20
4 30
1 40

90       

Những con bò đang thử phương pháp mới để trao đổi các tin nhắn được mã hóa với nhau, trong đó chúng trộn các chữ cái không liên quan vào giữa tin nhắn để làm cho các tin nhắn khó giải mã.

Những con bò truyền nhau hai xâu \(s\) và \(t\), mỗi xâu có độ dài tối đa \(10^5\) và chỉ bao gồm các chữ cái tiếng Anh viết thường từ a đến r. Để thử và hiểu thông điệp được mã hóa này, bạn sẽ nhận được truy vấn \(Q(1\leq Q\leq 10^5)\). Mỗi truy vấn cung cấp một tập hợp con các chữ cái tiếng Anh viết thường từ a đến r: Nếu chỉ giữ lại các chữ cái có trong tập con ở hai xâu \(s\) và \(t\) thì hai xâu có bằng nhau hay không.

Input

• Dòng đầu tiên chứa xâu \(s\).
• Dòng thứ hai chứa xâu \(t\).
• Dòng thứ ba chứa số \(Q\).
• \(Q\) dòng tiếp theo, mỗi dòng chứa một xâu truy vấn. Trong xâu được cho, không có chữ cái nào được lặp lại. Hơn nữa, tất cả các xâu truy vấn đều được sắp xếp theo thứ tự và không có xâu truy vấn nào xuất hiện nhiều lần.

Output

Với mỗi truy vấn, in ra Y nếu các kí tự được giữ lại ở \(2\) xâu tạo thành \(2\) xâu bằng nhau; ngược lại, in ra N.

Scoring

• Subtask \(1\): \(|s|,|t|,Q \leq 1000\).
• Subtask \(2\): Không có điều kiện gì thêm.

Example

aabcd
caabd
4
a
ac
abd
abcd

YNYN

Bessie tìm thấy một xâu \(s\) có độ dài tối đa là \(2*10^5\) chỉ chứa ba ký tự C, O và W. Cô ấy muốn biết liệu có thể biến xâu này thành C (chữ cái yêu thích của cô ấy) hay không bằng cách sử dụng các thao tác sau:

• \(1\): Chọn hai chữ cái liền kề giống nhau và xóa.
• \(2\): Chọn một chữ cái và thay thế nó bằng hai chữ cái còn lại theo thứ tự.

Việc tìm câu trả lời trên xâu \(s\) thôi là chưa đủ đối với Bessie, vì vậy cô ấy muốn biết câu trả lời cho \(Q(1 \leq Q\leq 2*10^5)\) xâu con của \(s\).

Input

• Dòng đầu tiên chứa xâu \(s\).
• Dòng tiếp theo chứa số \(Q\).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l,r\) \((1\leq l\leq r\leq |s|\), \(|s|\) là độ dài xâu \(s)\).

Output

Một xâu độ dài \(Q\), với ký tự thứ \(i\) là Y nếu xâu con thứ \(i\) có thể biến thành C và N nếu ngược lại.

Scoring

• Subtask \(1\): \(|s|,Q \leq 5000\).
• Subtask \(2\): Không có điều kiện gì thêm.

Example

COW
6
1 1
1 2
1 3
2 2
2 3
3 3

YNNNYN