Bài tập

Nước \(X\) là một đất nước rất xinh đẹp và giàu có. Ở đây có \(n\) thành phố, và một trong \(n\) thành phố đó chính là thủ đô của đất nước. Nước \(X\) đã có sẵn \(m\) con đường nối một chiều nối các thành phố. Tuy nhiên chính phủ nhận thấy rằng từ thủ đô, ta có thể không đến được một số thành phố. Vì vậy chính phủ quyết định xây thêm một số các con đường một chiều, sao cho sau khi xây xong, từ thủ đô có thể đến tất cả \(n - 1\) thành phố còn lại và số con đường xây thêm phải là ít nhất.

Với nhân lực hiện tại của chính phủ, họ chỉ có thể tính thủ công số con đường, vì vậy nếu số thành phố cực lớn thì họ không thể tính trong \(1\)s được. Vậy nên, các coder của đất nước, hãy viết chương trình tính toán số lượng con đường ít nhất cần phải xây.

Input

Dòng đầu tiên gồm \(3\) số nguyên dương \(n, m, s\) - số lượng thành phố, số con đường đã có, thủ đô của đất nước.

\(m\) dòng tiếp theo, mỗi dòng mô tả một con đường một chiều.

Output

Kết quả bài toán

Example

9 9 1
1 2
1 3
2 3
1 5
5 6
6 1
1 8
9 8
7 1

3

Scoring

\(30\%\) số test có \(n <= 20, m <= 30\).

\(30\%\) số test có \(n, m <= 5000\).

\(40\%\) số test còn lại \(n, m <= 2.10^5\).

Trong một hệ thống xử lý tín hiệu số, có \(n\) bộ phát được đánh số từ \(1\) đến \(n\). Bộ phát thứ \(i\) có cường độ tín hiệu là \(a_i\).

Mỗi mã truy vấn \(x\) biểu diễn một tập các đặc tính tín hiệu cần thiết dưới dạng nhị phân. Một bộ phát thứ \(i\) được xem là tương thích với mã \(x\) nếu nó chứa đầy đủ tất cả các bit \(1\) xuất hiện trong biểu diễn nhị phân của \(x\).

Nói cách khác, bộ phát thứ \(i\) tương thích với \(x\) khi \(x & i = x\), trong đó \(&\) là phép toán AND trên bit.

Với mỗi số nguyên dương \(x\), ta định nghĩa trọng số của \(x\) là:

tức là tổng cường độ của tất cả các bộ phát thứ \(i\) thỏa mãn \(x & i = x\).

Yêu cầu: Hãy tính lần lượt các giá trị \(f(1), f(2), \ldots, f(2^{\lfloor \log_2 n \rfloor + 1} - 1)\).

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) — số lượng bộ phát \((1 \leq n \leq 10^6)\).

• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) — cường độ tín hiệu của các bộ phát \((|a_i| \leq 10^9)\).

Output

• In ra lần lượt các giá trị \(f(1), f(2), \ldots, f(2^{\lfloor \log_2 n \rfloor + 1} - 1)\) trên một dòng, các giá trị cách nhau bởi một dấu cách.

Example

3
3 2 1

4 3 1 

Scoring

• Subtask 1 (30 điểm): \(1 \leq n \leq 1000\).

• Subtask 2 (30 điểm): \(1 \leq n \leq 100000\).

• Subtask 3 (40 điểm): Không có ràng buộc gì thêm.

Trên hành tinh Pandora, chủng tộc Navi đang phải đối mặt với cuộc xâm lăng của người Trái Đất. Người Trái Đất đã cử \(n\) robot với lượng máu tương ứng là \(a_1, a_2, \ldots, a_n\). Để bảo vệ quê hương, \(m\) dũng sĩ Navi đã ra trận, mỗi dũng sĩ thứ \(j\) có sức tấn công là \(b_j\).

Theo tín ngưỡng của người Navi, họ yêu chuộng hòa bình nên mỗi dũng sĩ chỉ tấn công một robot duy nhất. Một dũng sĩ Navi thứ \(j\) có thể tiêu diệt được một robot thứ \(i\) nếu sức tấn công của dũng sĩ đó lớn hơn hoặc bằng lượng máu của robot (\(b_j \ge a_i\)).

Với danh sách lượng máu của \(n\) robot và sức tấn công của \(m\) dũng sĩ Navi, hãy tìm số lượng robot tối đa mà các dũng sĩ Navi có thể tiêu diệt.

Input

Dữ liệu vào được cung cấp từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(m\) (\(1 \le n, m \le 10^6\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^9\)), là lượng máu của các robot.
• Dòng thứ ba chứa \(m\) số nguyên dương \(b_1, b_2, \ldots, b_m\) (\(1 \le b_j \le 10^9\)), là sức tấn công của các dũng sĩ Navi.

Output

Số lượng Robot nhiều nhất mà các chiến binh Navi có thể tiêu diệt được (Lưu ý: mỗi chiến binh Navi chỉ tấn công một robot duy nhất)

Example

3 2
1 2 3
1 1

1

Scoring

• Subtask 1 (10% số điểm): \(a_i = b_j = 1\) với mọi \(1 \le i \le n\) và \(1 \le j \le m\).
• Subtask 2 (30% số điểm): \(b_1 = b_2 = \dots = b_m\).
• Subtask 3 (60% số điểm): Không có ràng buộc bổ sung.

Cho dãy số \(a_1, a_2, \ldots, a_n\). Ta có định nghĩa median của một dãy số như sau:

• Nếu độ dài dãy là lẻ thì median = phần tử giữa của dãy sau khi sắp xếp. Ví dụ \(a = \{1, 2, 3\}\) thì median = 2.
• Nếu độ dài dãy là chẵn thì median = trung bình cộng của hai phần tử giữa của dãy sau khi sắp xếp. Ví dụ \(a = \{1, 2, 3, 4\}\) thì median = 2.5.

Yêu cầu: Cho \(n\) số nguyên, với mỗi lần nhập \(a_i\), bạn phải thực hiện:

• Thêm \(a_i\) vào dãy số.
• Tính median cho dãy số mới cập nhật.
• In ra median của các dãy số mới cập nhật trên từng dòng, mỗi median in ra theo định dạng 1 chữ số thập phân sau dấu phẩy.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) \((1 \leq n \leq 10^5)\).
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa số nguyên \(a_i\) \((0 \leq a_i \leq 10^5)\).

Output

• Ghi ra \(n\) số thực trên \(n\) dòng theo thứ tự là median của các dãy số.

Example

6
12
4
5
3
8
7

12.0
8.0
5.0
4.5
5.0
6.0

Scoring

• \(20\%\) số test có \(n \leq 100\).
• \(30\%\) số test có \(n \leq 1000\).
• \(20\%\) số test có dãy \(a\) là \(1\) dãy tăng dần.
• \(30\%\) còn lại không có ràng buộc gì thêm.