Thư viện STL, đếm cơ bản

Một cửa hàng kinh doanh đang quản lý kho hàng của mình với \(N\) sự kiện diễn ra tuần tự. Mỗi sự kiện thuộc một trong hai loại sau:

• 1 x: Thêm một món hàng có mã số \(x\) vào gian hàng.
• 2 x: Khách hàng yêu cầu mua món hàng có mã số \(x\). Nếu món hàng này đang có sẵn trên gian hàng, in ra YES. Ngược lại, in ra NO.

Hãy viết chương trình mô phỏng lại quá trình bán hàng trên.

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) là số lượng sự kiện.
• \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(type\) và \(x\) mô tả một sự kiện.

Output

• Với mỗi sự kiện loại \(2\), in ra YES hoặc NO trên một dòng tương ứng với kết quả kiểm tra.

Constraints

• \(1 \le N \le 2 \cdot 10^5\)
• \(1 \le x \le 10^9\)

Example

6
1 5
1 10
2 5
2 7
1 7
2 7

YES
NO
YES

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(N \le 10^3, x \le 10^3\).
• Subtask \(2\) (\(60\%\) số điểm): Không có ràng buộc gì thêm.

Một cửa hàng kinh doanh buông bán v.v. Có \(N\) sự kiện diễn ra:
Các sự kiện gồm một trong hai loại:

• 1 a x: Thêm \(a\) món hàng \(x\) vào gian hàng
• 2 b x: Khách yêu cầu mua \(b\) món hàng \(x\), nếu có trên gian hàng (số lượng hiện có lớn hơn hoặc bằng \(b\)) thì in ra YES, ngược lại in ra NO.

Input

• Dòng đầu tiên chứa số nguyên \(N\) (\(1 \le N \le 10^5\)) là số lượng sự kiện.
• \(N\) dòng tiếp theo, mỗi dòng mô tả một sự kiện theo định dạng 1 a x hoặc 2 b x. Trong đó \(a, b\) là các số nguyên dương và \(x\) là tên món hàng (chuỗi ký tự có độ dài không quá 5).

Output

• Với mỗi sự kiện loại 2, in ra YES hoặc NO trên một dòng tùy thuộc vào kết quả kiểm tra.

Example

4
1 5 keo
2 3 keo
2 6 keo
1 2 keo

YES
NO

Trong một buổi chiều hè đầy nắng, Tí và Tèo tham gia một trò chơi thử thách trí tuệ do các bạn trong câu lạc bộ Tin học tổ chức. Ban tổ chức trao cho Tí một dãy gồm \(n\) số nguyên \(a_1, a_2, \dots, a_n\) và một số nguyên \(x\).

Thử thách đặt ra là Tí phải xem xét tất cả các đoạn con liên tiếp có độ dài đúng bằng \(k\) của dãy số này, và đếm xem tổng cộng có bao nhiêu lần giá trị \(x\) xuất hiện trong tất cả các đoạn con đó. Tèo liền nhanh trí viết một chương trình để tính toán nhanh kết quả này nhằm giành phần thưởng. Bạn hãy giúp Tèo hoàn thành chương trình nhé!

Input

• Dòng đầu tiên chứa ba số nguyên \(n, k, x\) (\(1 \le k \le n \le 10^5\), \(|x| \le 10^9\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(|a_i| \le 10^9\)).

Output

• In ra một số nguyên duy nhất là tổng số lần xuất hiện của giá trị \(x\) trong tất cả các đoạn con có độ dài \(k\) của dãy \(a\).

Example

5 3 2
1 2 2 3 2

6

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n, k \le 10^3\).
• Subtask \(2\) (\(30\%\) số điểm): \(n, k \le 5 \cdot 10^4\).
• Subtask \(3\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Cho một dãy gồm \(n\) số nguyên \(a_1, a_2, a_3, \dots, a_n\) và một số nguyên \(K\). Alice và Bob đang cùng nhau phân tích các đoạn con liên tiếp của dãy số này. Với mỗi đoạn con có độ dài \(K\) (xét theo thứ tự chỉ số bắt đầu của đoạn tăng dần), hãy in ra màn hình giá trị nhỏ nhất (min) và lớn nhất (max) của đoạn đó trên một dòng.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(K\) (\(1 \le K \le n \le 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, a_3, \dots, a_n\)

Output

• Gồm nhiều dòng, mỗi dòng chứa hai số nguyên lần lượt là giá trị min và max của đoạn con độ dài \(K\) tương ứng theo thứ tự chỉ số bắt đầu tăng dần.

Example

5 3
1 3 -1 -3 5

-1 3
-3 3
-3 5