Thư viện STL

Bưu điện trung tâm vừa nhận được \(N\) gói hàng. Mỗi gói hàng có một mã số (\(ID\)) và mã vùng nhận (\(RegionID\)) tương ứng. Bạn hãy giúp nhân viên bưu điện xếp các gói hàng này vào đúng giỏ của từng vùng.

Giả sử có \(M\) vùng (đánh số từ \(1\) đến \(M\)). Với mỗi gói hàng có (\(ID, RegionID\)), hãy thêm \(ID\) vào danh sách của vùng tương ứng.

Input

• Dòng 1: \(N\) (số gói hàng) và \(M\) (số vùng).
• \(N\) dòng tiếp theo: Mỗi dòng chứa 2 số nguyên \(ID\) và \(RegionID\).

Output

• In ra danh sách các \(ID\) gói hàng trong từng vùng (mỗi vùng 1 dòng theo định dạng ví dụ).

Constraints

• \(1 \le N, M \le 10^5\)
• \(1 \le ID \le 10^9\)
• \(1 \le RegionID \le M\)

Example

5 3
101 1
102 2
103 3
104 3
105 1

Vung 1: 101 105
Vung 2: 102
Vung 3: 103 104

Một robot thám hiểm di chuyển lần lượt qua \(N\) trạm kiểm soát theo thứ tự từ \(1\) đến \(N\). Bạn được cho tọa độ \((x, y)\) của từng trạm. Hãy tính tổng quãng đường mà robot đã di chuyển.

Quy ước: Khoảng cách giữa hai điểm \(A(x_A, y_A)\) và \(B(x_B, y_B)\) được tính theo công thức Manhattan:

Để giải quyết bài toán này, bạn cần hiện thực một hàm tính khoảng cách Manhattan giữa hai điểm và sử dụng nó để tính tổng quãng đường.

Template

Học sinh nên thiết kế hàm tính khoảng cách có dạng như sau:

    long long distance(pair<int, int> a, pair<int, int> b) {
        // Hoàn thiện hàm tính khoảng cách Manhattan
    }

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) là số lượng trạm kiểm soát.
• \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x_i, y_i\) là tọa độ của trạm kiểm soát thứ \(i\).

Output

• Một số nguyên duy nhất là tổng quãng đường di chuyển của robot qua \(N\) trạm theo đúng thứ tự.

Constraints

• \(1 \le N \le 10^5\)
• \(-10^9 \le x_i, y_i \le 10^9\)

Example

3
0 0
0 2
2 2

4

Trong một vương quốc nọ, Quốc vương quyết định tổ chức một bữa tiệc linh đình và mời tất cả thần dân tham dự. Mỗi người dân khi đến cổng hoàng cung đều được phát một tấm thẻ ghi một con số may mắn \(a_i\). Tuy nhiên, vì quá đông người, có rất nhiều người nhận được những con số giống hệt nhau.

Để chuẩn bị quà tặng một cách khoa học, Quốc vương yêu cầu quan Tể tướng phải thống kê lại danh sách các con số may mắn đã được phát ra. Quan Tể tướng cần phải lọc bỏ các con số trùng lặp và liệt kê chúng theo thứ tự từ nhỏ đến lớn. Bạn hãy giúp quan Tể tướng hoàn thành nhiệm vụ này nhé!

Input

• Dòng đầu tiên chứa số nguyên dương \(n\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) cách nhau bởi dấu cách.

Output

• Một dòng duy nhất chứa các giá trị phân biệt xuất hiện trong mảng \(a\) theo thứ tự tăng dần, các số cách nhau bởi dấu cách.

Constraints

• \(1 \le n \le 10^5\)
• \(|a_i| \le 10^9\)

Example

6
5 1 2 5 2 3

1 2 3 5

4
10 10 10 10

10

Tí và Tèo rất yêu thích toán học, đặc biệt là các phép toán trên tập hợp. Một ngày nọ, Tí đưa cho Tèo hai tập hợp số nguyên \(A\) và \(B\). Tí thách đố Tèo thực hiện ba phép toán cơ bản sau đây trên hai tập hợp này:

1. Phép giao (\(A \cap B\)): Tìm các phần tử xuất hiện ở cả hai tập hợp.
2. Phép hiệu (\(A \setminus B\)): Tìm các phần tử xuất hiện trong tập hợp \(A\) nhưng không có trong tập hợp \(B\).
3. Phép hợp (\(A \cup B\)): Tìm các phần tử xuất hiện ở ít nhất một trong hai tập hợp \(A\) hoặc \(B\).

Các phần tử trong mỗi tập hợp kết quả phải được liệt kê theo thứ tự tăng dần. Bạn hãy giúp Tèo hoàn thành thử thách này nhé!

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) lần lượt là số lượng phần tử của tập hợp \(A\) và tập hợp \(B\).
• Dòng thứ hai chứa \(n\) số nguyên phân biệt của tập hợp \(A\).
• Dòng thứ ba chứa \(m\) số nguyên phân biệt của tập hợp \(B\).

Output

• Dòng thứ nhất: In ra các phần tử của tập hợp \(A \cap B\) theo thứ tự tăng dần.
• Dòng thứ hai: In ra các phần tử của tập hợp \(A \setminus B\) theo thứ tự tăng dần.
• Dòng thứ ba: In ra các phần tử của tập hợp \(A \cup B\) theo thứ tự tăng dần.

Constraints

• \(1 \leq n, m \leq 10^5\)
• Giá trị các phần tử trong tập hợp có trị tuyệt đối không quá \(10^9\).

Example

5 4
1 2 3 4 5
3 4 5 6

3 4 5
1 2
1 2 3 4 5 6

3 3
10 20 30
40 50 60

10 20 30
10 20 30 40 50 60