Phổ Thống Trị Ba Chiều · canuc80k6000

Description

Có $n$ phần tử, phần tử thứ $i$ mang ba thuộc tính nguyên $(a_{i}, b_{i}, c_{i})$ . Với mỗi $i$ , gọi $f_{i}$ là số chỉ số $j \neq = i$ thỏa đồng thời $a_{j} \leq a_{i}, b_{j} \leq b_{i}$ và $c_{j} \leq c_{i}$ . Hãy lập phân bố của các giá trị $f_{i}$ .

Input

Dòng đầu chứa $n$ và $k$ .
$n$ dòng tiếp theo chứa ba số nguyên $a_{i}, b_{i}, c_{i}$ .

Output

In $n$ dòng; dòng thứ $d + 1$ là số phần tử có đúng $d$ phần tử khác không lớn hơn nó trên cả ba tọa độ.

Constraints

$1 \leq n \leq 1 0^{5}$ .
$1 \leq a_{i}, b_{i}, c_{i} \leq k \leq 2 \cdot 1 0^{5}$ .

Scoring

Subtask $1$ ( $50%$ số điểm): dữ liệu nhỏ theo giới hạn được công bố trong hệ thống chấm.
Subtask $2$ ( $50%$ số điểm): không có giới hạn bổ sung.

Example

Test 1

Input

Output

Giải thích: Hai phần tử $(1, 1, 1)$ cùng có đúng một phần tử khác không lớn hơn mình; hai phần tử ở giữa cùng có kết quả $2$ , còn $(3, 3, 3)$ có kết quả $4$ . Vì thế các tần suất lần lượt là $0, 2, 2, 0, 1$ .

Mô hình và thuật toán: Sắp xếp và gộp các bộ ba trùng nhau. CDQ theo tọa độ thứ nhất; khi ghép, quét tọa độ thứ hai và dùng Fenwick trên tọa độ thứ ba để cộng số bản sao từ nửa trái sang nửa phải.
Chứng minh tính đúng đắn: Mỗi cặp thuộc hai nhóm khác nhau được xử lý đúng tại nút CDQ thấp nhất tách chúng sang hai nửa. Điều kiện quét và tổng tiền tố Fenwick kiểm tra chính xác hai tọa độ còn lại; phần tử trùng được bù bằng multiplicity trừ một.
Độ phức tạp: O(n log² n) thời gian và O(n+k) bộ nhớ.
Lỗi thường gặp: Một lỗi tự nhiên là dùng bất đẳng thức nghiêm ngặt và bỏ sót các tọa độ bằng nhau.