Bài tập

Viết chương trình nhập vào từ bàn phím số nguyên dương \(n\). In ra màn hình các số nguyên dương có giá trị nhỏ hơn hoặc bằng \(n\).

Example

5

1 2 3 4 5 

10

1 2 3 4 5 6 7 8 9 10 

Cho một dãy \(a\) gồm \(n\) số nguyên dương \(a_{1}, a_{2}, a_{3}, ..., a_{n}\) \((a_{i} \leq 10^9)\).

Yêu cầu:
Có \(q\) truy vấn có dạng \(l, r, d\). Với mỗi truy vấn, bạn cần đếm xem có bao nhiêu đoạn con nằm trong đoạn từ \(l\) đến \(r\) có ước chung lớn nhất không vượt quá \(d\). Nói một cách cụ thể hơn, hãy đếm xem có bao nhiêu cặp \((u, v)\) sao cho:

• \(l \leq u \leq v \leq r\).
• \(gcd(a_{u}, a_{u + 1}, a_{u + 2}, ..., a_{v}) \leq d\).

Input

• Dòng đầu tiên là \(2\) số \(n\) và \(q\) \((1 \leq n, q \leq 2.10^5)\).
• Dòng tiếp theo chứa \(n\) số nguyên dương \(a_{1}, a_{2}, a_{3}, ..., a_{n}\) \((a_{i} \leq 10^9)\).
• \(q\) dòng tiếp theo, mỗi dòng chứa ba số \(l, r, d\).

Output

• Với mỗi truy vấn, in kết quả ra trên một dòng.

Example

6 5
3 9 6 2 8 4
1 5 3
2 4 3
1 5 4
2 6 2
1 6 1

12
4
12
9
6

Scoring

• \(20\%\) số test có \(n, q \leq 100\).
• \(30\%\) số test có \(n, q \leq 1000\).
• \(30\%\) số test có \(d\) là hằng số, \(n, q \leq 100000\) (với mọi truy vấn, \(d\) luôn không thay đổi).
• \(20\%\) số test còn lại không có ràng buộc gì thêm.

Cho hai bảng nhị phân \(a\) và \(b\) có cùng kích thước \(n\)x\(n\). Bảng nhị phân là bảng chứa các phần tử là \(0\) hoặc \(1\). Có hai loại thao tác có thể thực hiện được trên bảng:

• thao tác \(1\): Chọn một hàng bất kì và thực hiện đảo ngược tất cả các số ở trên hàng. Ví dụ: hàng \(x\) lần lượt là \(0, 0, 0, 1, 0, 1\), sau khi thực hiện thao tác thứ nhất, hàng \(x\) trở thành \(1, 1, 1, 0, 1, 0\).
• thao tác \(2\): Chọn một cột bất kì và thực hiện đảo ngược tất cả các số ở trên cột. Ví dụ: cột \(x\) lần lượt là \(0, 0, 0, 1, 0, 1\), sau khi thực hiện thao tác thứ nhất, cột \(x\) trở thành \(1, 1, 1, 0, 1, 0\).

Thao tác loại \(1\) và thao tác loại \(2\) có thể thực hiện với số lần bất kì (có thể \(0\)). Hãy kiểm tra xem có cách nào sau khi thực hiện các thao tác, bảng \(a\) trở thành bảng \(b\).

Input

Dòng đầu tiên gồm số nguyên dương \(Q\) \((Q <= 5)\) là số truy vấn.

Với mỗi truy vấn, dòng đầu tiên là số nguyên dương \(n\) - kích thước của \(2\) bảng \(a\), \(b\).

\(n\) dòng tiếp theo, mỗi dòng mô tả một hàng của bảng \(a\).

\(n\) dòng tiếp theo, mỗi dòng mô tả một hàng của bảng \(b\).

Output

\(Q\) dòng, mỗi dòng in ra "YES" nếu có thể đưa được bảng \(a\) trở thành bảng \(b\), in "NO" ngược lại.

Example

1
3
1 1 0
0 0 1
1 1 0

0 0 0
0 0 0
0 0 0

YES

Scoring

\(30\%\) số test có \(n <= 10\), \(Q = 1\).

\(15\%\) số test có \(n <= 100\), nếu có thể đưa bảng \(a\) về bảng \(b\) thì sẽ tồn tại cách dùng không quá hai thao tác.

\(15\%\) số test có \(n <= 1000\), nếu có thể đưa bảng \(a\) về bảng \(b\) thì sẽ tồn tại cách dùng không quá hai thao tác.

\(40\%\) số test còn lại có \(n <= 1000\).

Cho một đồ thị vô hướng liên thông có trọng số gồm \(n\) đỉnh, \(m\) cạnh. Cạnh thứ \(i\ (1 \le i \le m)\) nối hai đỉnh \(u_i\) và \(v_i\ (1 \le u_i \neq v_i \le n)\) với trọng số là \(2^i\).

Yêu cầu: Cho \(k\) đỉnh đặc biệt \(s_1, s_2, \ldots, s_k\), hãy chọn ra các cạnh với tổng trọng số nhỏ nhất
để liên thông được \(k\) đỉnh.

Input

• Dòng đầu chứa ba số \(n, m, k\ (n, m, k \le 3.10^5)\).
• Dòng thứ \(i\) trong \(m\) dòng, mỗi dòng chứa hai số \(u_i, v_i\).
• Dòng cuối cùng chứa \(k\) số nguyên mô tả \(k\) đỉnh đặc biệt.

Output

• Gồm một dòng chứa \(m\) số, số thứ \(i\) bằng số \(1\) hoặc \(0\) tương ứng là cạnh thứ \(i\) được chọn hoặc không được chọn.

Example

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

0 1 1 0