Bài tập

Cho một dãy \(n\) số \(a_{1},a_{2},...,a_{n}\) và \(1\) số \(m\) sao cho \(0 \leq a_{i} < 2^m\) . Với mỗi \(i\) từ \(1\) đến \(n\) và \(k\) từ \(k\) từ \(0\) đến \(m\) hãy in ra số số \(j\) sao cho \(1 \leq j < i\) mà \(dis(a_{i},a_{j})=k\) Trong đó \(dis(x,y)\) là số số bit được bật trong đúng một trong \(2\) biểu diễn nhị phân của \(x\), \(y\) .

Input

• Dòng đầu chứa số \(n\) và \(m\) \((1 \leq n \leq 2e5, 1 \leq m \leq 16)\). Dòng sau chứa \(n\) số \(a_{1},a_{2},...,a_{n}\) .

• Dòng thứ hai chứa \(n\) số \(a_{1}, a_{2}, ..., a_{n}\).

Output

\(n\) dòng mỗi dòng \(m + 1\) số là đáp án của \(k = 0, 1, ...,m\).

Example

4 2
0 1 2 3

0 0 0 
0 1 0 
0 1 1 
0 2 1 

4 1
0 1 1 0

0 0 
0 1 
1 1 
1 2 

Scoring

\(30\%\) số test có \(n \leq 1000\).

\(30\%\) số test có \(m \leq 8\).

\(40\%\) số test còn lại không có ràng buộc gì thêm.

Cây là đồ thị vô hướng liên thông không có chu trình. Bài toán này cho một cây không có gốc.
Lá của cây là đỉnh chỉ kết nối với nhiều nhất một đỉnh khác.

Quân là một thợ mộc lành nghề, đến nay tuổi nghề cũng đã được 16 năm. Hiện tại, Quân vừa mới đi rừng về, đào được một cái cây có \(n\) đỉnh. Giờ Quân muốn xử lí cái cây này. Để làm điều đó, trong một thao tác, Quân loại bỏ tất cả các lá của cây.

Ví dụ ta có một cây như sau:

\begincenter

\endcenter

Sau một thao tác:

\begincenter

\endcenter

Chú ý một số trường hợp đặc biệt sau:

• nếu cây không có đỉnh nào thì thao tác nào cũng không thay đổi cây

• nếu cây còn duy nhất một đỉnh thì đỉnh đấy sẽ bị loại bỏ

• nếu cây còn lại hai đỉnh thì hai đỉnh đấy đồng thời bị loại bỏ.

Quân liên tục thực hiện thao tác như vậy đúng \(k\) lần. Hỏi, sau \(k\) thao tác, cây còn lại bao nhiêu đỉnh ?

Input

Dòng đầu tiên gồm 2 số \(n, k\) - số lượng đỉnh của cây và số lượng thao tác.

\(n - 1\) dòng tiếp theo, mỗi dòng chứa \(2\) số mô tả cạnh của cây.

Output

Một dòng, kết quả bài toán

Example

14 1
1 2
2 3
2 4
4 5
4 6
2 7
7 8
8 9
8 10
3 11
3 12
1 13
13 14

7

Scoring

Có 30 phần trăm số test có \(n, k <= 10^3\)

Có 20 phần trăm số test cây có dạng đường thẳng.

50 phần trăm số test còn lại \(n, k <= 4.10^5\)

Nhà khoa học Alex đang thực hiện một cuộc thám hiểm để nghiên cứu các mẫu vật tại \(n\) địa điểm khác nhau. Anh ấy bắt đầu chuyến đi từ địa điểm \(1\). Giữa một số địa điểm có các con đường bộ hai chiều, và Alex biết thời gian cần thiết để đi qua mỗi con đường.

Ngoài ra, giữa mỗi cặp địa điểm còn có một tuyến đường hàng không, nhưng do một sự cố kỹ thuật gần đây, thời gian di chuyển giữa hai địa điểm \(u\) và \(v\) bằng đường hàng không được tính bằng \((u - v)^2\).

Vì Alex không thích bay cho lắm, anh ta chỉ có thể sử dụng tối đa \(k\) chuyến bay trong suốt hành trình của mình. Mục tiêu của Alex là tìm thời gian di chuyển tối thiểu từ địa điểm \(1\) đến mỗi địa điểm khác.

Yêu cầu: Hãy giúp Alex tính toán thời gian di chuyển tối thiểu từ địa điểm \(1\) đến mỗi địa điểm trong số \(n\) địa điểm.

Input

• Dòng đầu tiên của input chứa ba số nguyên \(n, m, k\) (\(2 \le n \le 10^5, 1 \le m \le 10^5, 0 \le k \le 20\)) lần lượt là số địa điểm, số con đường bộ và số chuyến bay tối đa mà Alex có thể sử dụng.
• \(m\) dòng tiếp theo mô tả các con đường bộ. Mỗi dòng chứa ba số nguyên \(u, v, w\) (\(1 \le u, v \le n, u \ne v, 1 \le w \le 10^9\)) --- hai địa điểm được kết nối và thời gian di chuyển qua con đường đó. Lưu ý rằng một số cặp địa điểm có thể được kết nối bởi nhiều hơn một con đường.

Output

• In ra \(n\) số nguyên, số thứ \(i\) là thời gian di chuyển tối thiểu đến địa điểm \(i\).

Example

3 1 2
1 3 1

0 1 1 

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

0 1 4 6 

Scoring

• Subtask \(1\) (25% số điểm) : \(k = 0\).
• Subtask \(2\) (25% số điểm) : \(n, m \leq 50\).
• Subtask \(3\) (25% số điểm) : Đồ thị có dạng đường thẳng.
• Subtask \(4\) (25% số điểm) : Không có ràng buộc gì thêm.

Trong giờ học Vật lý, một thành viên của CLB CHTCoder đang lơ đãng nhớ về crush thì bị thầy phát hiện.

Để không bị trừ điểm hoặc ghi vào sổ đầu bài, thầy đã giao cho hai bạn một thử thách:
Cho một bảng kích thước \(n \times n\), trong đó các số được điền theo thứ tự tăng dần từ trái sang phải và từ trên xuống dưới, bắt đầu từ \(1\) cho tới \(n \times n\).

Yêu cầu của thầy rất đơn giản: Tính tổng các phần tử nằm trên đường chéo chính của bảng.

Input

Đọc từ file NHOEM.INP:

• Số nguyên dương \(t\) (\(1 \le t \le 10^{6}\)) --- số câu hỏi.
• Mỗi dòng tiếp theo chứa một số nguyên dương \(n\) (\(1 \le n \le 10^{6}\)).

Output

Ghi ra file NHOEM.OUT:

• Gồm \(t\) dòng, mỗi dòng là tổng đường chéo chính tương ứng.

Example

2
3
6

15
111

Scoring

• Subtask 1 (70%): \(1 \le t, n \le 10^{3}\).
• Subtask 2 (30%): Không có ràng buộc thêm.