Bài tập

Trong mặt phẳng tọa độ, cho hai đoạn thẳng. Đoạn thẳng thứ nhất được xác định bởi hai điểm đầu mút \(P_1=(x_1, y_1)\) và \(P_2=(x_2, y_2)\). Đoạn thẳng thứ hai được xác định bởi hai điểm đầu mút \(P_3=(x_3, y_3)\) và \(P_4=(x_4, y_4)\).

Nhiệm vụ của bạn là xác định xem hai đoạn thẳng này có cắt nhau hay không, tức là chúng có ít nhất một điểm chung.

Bạn phải trả lời \(t\) truy vấn có dạng như trên.

Input

• Dòng đầu tiên chứa một số nguyên dương \(t\) (\(1 \le t \le 10^5\)), là số lượng các truy vấn.
• \(t\) dòng tiếp theo, mỗi dòng chứa tám số nguyên \(x_1, y_1, x_2, y_2, x_3, y_3, x_4, y_4\) (\(-10^9 \le x_i, y_i \le 10^9\)) mô tả hai đoạn thẳng.

Output

• Với mỗi truy vấn, in ra trên một dòng:

• YES nếu hai đoạn thẳng có điểm chung.

• NO nếu ngược lại.

Example

5
1 1 5 3 1 2 4 3
1 1 5 3 1 1 4 3
1 1 5 3 2 3 4 1
1 1 5 3 2 4 4 1
1 1 5 3 3 2 7 4

NO
YES
YES
YES
YES

Phù thủy Merlin đang huấn luyện phép thuật bit với học trò. Anh ta bắt đầu với một con số ma thuật \(a = 0\) và thực hiện \(q\) phép biến đổi thuộc một trong các loại sau:

• Phép XOR ma thuật: "1 \(x\)" - Biến đổi \(a\) thành \(a \oplus x\) (phép XOR với \(x\))
• Phép triệt tiêu bit quyền lực: "2" - Tắt bit mạnh nhất (MSB) của \(a\). Nếu \(a = 0\), bỏ qua phép thuật này
• Phép đếm năng lượng: "3" - Đếm số bit bật (số lượng năng lượng) trong \(a\)

Bit mạnh nhất (MSB): Là bit bật nằm tận cùng bên trái. Ví dụ với số \(36\) (nhị phân: \(100100_2\)), MSB là bit thứ 5, sau khi tắt được \(4\) (\(100_2\))

Input

• Dòng đầu tiên gồm một số nguyên \(q\).
• \(q\) dòng tiếp theo, mỗi dòng gồm một truy vấn theo định dạng trên.

Output

• In ra đáp án là một số nguyên cho mỗi truy vấn loại \(3\).

Example

5
2
1 5
3
2
3

2
1

Một dãy số Double là dãy số nguyên có \(2k\) phần tử \(x_1, x_2, \ldots, x_{2k}\) (\(k\) nguyên), có \(k\) phần tử bên trái và \(k\) phần tử bên phải. Nếu có cách ghép \(k\) phần tử bên trái với \(k\) phần tử bên phải tạo thành \(k\) cặp mà mỗi cặp là hai số giống nhau. Ví dụ dãy số \(1 \ 2 \ 3 \ 3 \ 1 \ 2\) và dãy số \(1 \ 1 \ 2 \ 3 \ 2 \ 3 \ 1 \ 1 \ 2 \ 2\) là các dãy số Double, nhưng dãy số \(1 \ 1 \ 2 \ 2\) không phải là dãy số Double.

Vinh có dãy \(N\) số nguyên \(a_1, a_2, \ldots, a_N\) (\(1 \le a_i \le N\), \(N\) chẵn), có \(L\) số đầu tiên ở tập số bên trái và \(R\) số tiếp theo ở tập số bên phải (\(L+R = N\)). Để biến đổi dãy số trên thành dãy số Double, Vinh có thể thực hiện số lần biến đổi không hạn chế. Mỗi lần biến đổi được thực hiện bằng một trong ba cách sau:

• Thay đổi giá trị \(a_i\) thành giá trị \(b_i\) (\(1 \le b_i \le N\)).
• Di chuyển một số từ tập số bên trái sang tập số bên phải và giữ nguyên giá trị.
• Di chuyển một số từ tập số bên phải sang tập số bên trái và giữ nguyên giá trị.

Ví dụ: Vinh có dãy số \(1 \ 1 \ 2 \ 2 \ 2 \ 2\) với \(L=2\) và \(R=4\) thì số lần biến đổi ít nhất là 3: trong đó số 2 ở tập số bên phải di chuyển về tập số bên trái, thay đổi hai số 1 ở tập số bên trái thành hai số 2 (hoặc thay đổi hai số 2 tập số bên phải thành hai số 1).

Yêu cầu: Tính số lần biến đổi ít nhất để dãy số trên thành dãy số Double.

Input

• Dòng đầu tiên có một số \(T\) là số lượng test (\(T \le 10\)).

• Mỗi test có cấu trúc như sau:

• Dòng đầu ghi ba số nguyên \(N, L, R\) trong đó \(1 \le N \le 200000\), \(L+R=N\).

• Dòng tiếp theo ghi \(N\) số \(a_1, a_2, \ldots, a_N\) (\(1 \le a_i \le N\)).
• Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

• Ghi ra \(T\) dòng, mỗi dòng ghi số lần biến đổi tương ứng với mỗi test theo yêu cầu bài toán.

Example

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

2
3
5

Scoring

• Có \(50\%\) số điểm tương ứng với \(L=R\);
• Có \(50\%\) số điểm tương ứng với \(N \le 200000\).

Nam có \(N\) đồng tiền được đánh số từ \(1\) đến \(N\), đồng tiền thứ \(i\) có mệnh giá là \(T_i\) (\(1 \le i \le N\)).

Siêu thị có \(M\) mặt hàng được đánh số từ \(1\) đến \(M\), mặt hàng thứ \(j\) được bán với giá là \(P_j\) (\(1 \le j \le M\)).

Yêu cầu: Hãy xác định với mỗi mặt hàng trong siêu thị Nam có thể sử dụng các đồng tiền hiện có của mình để mua được hay không với điều kiện là trả đúng giá và không lấy lại tiền thối.

Input

• Dòng đầu ghi số nguyên dương \(N\) và \(M\);
• Dòng thứ hai ghi \(N\) số nguyên dương \(T_1,T_2,...,T_N\);
• Dòng thứ ba ghi \(M\) số nguyên dương \(P_1,P_2,...,P_M\);
• Các số có giá trị không quá \(10^6\) và được ghi cách nhau ít nhất một dấu cách.

Output

• Gồm \(M\) dòng ghi kết quả tương ứng của từng mặt hàng: YES nếu có
  thể mua được, ngược lại ghi NO.

Example

3 4
1 2 6
1 2 3 5

YES
YES
YES
NO

Scoring

• Có \(50\%\) số điểm \(N \le 15\) và \(M \le 100\);
• Có \(50\%\) số điểm \(15 < N \le 20\) và \(M \le 100 000\).