<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

394. Berhatton
Time limit per test: 1.5 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



Berhatton is one of the most picturesque districts of Berland. All streets in Berhatton are parallel to the coordinate axes. All streets are really long, so you can consider them infinite. Any point with integer coordinates is an intersection of two streets. So the whole plane is divided by streets into one-unit squares. All squares are occupied by the sky-scrappers. Due to this fact, the distance between point (x1, y1) and point (x2, y2) is equal to |x1 - x2| + |y1 - y2|. BerPizza company has been working in Berhatton for a while and has N pizza huts. In each pizza hut they can make any kind of pizza from the menu and deliver it to the customer. Unfortunately, the company doesn't have enough funds to buy cars or even bikes for pizza delivery, so pizza boys have to deliver pizza on foot. Pizza boys from different huts run with the different speed. Everybody knows the famous motto of BerPizza "Deliver pizza in 10 minutes", so pizza boys have to move fast.

Nowadays BerPizza company has a hard time, because hamburgers become more and more popular. BerPizza has even decided to close some of their huts because of financial problems. BerPizza president has made a rush decision that the pizza hut A can be closed if pizza boys from at least K other pizza huts can reach it in 10 minutes. Your task is to find numbers of pizza huts, which can be closed.

Input
The first line of the input contains two integer numbers N and K (2 ≤ N ≤ 105, 1 ≤ K ≤ N - 1). The following N lines contain coordinates of pizza huts x, y, and number w — the amount of unit segments pizza boy can cover in 10 minutes (0 ≤ x ≤ 109, 0 ≤ y ≤ 109, 1 ≤ w ≤ 109).

Output
Print the number of pizza huts T which can be closed to the first line of the output file. The next line should contain T numbers — the numbers of pizza huts that need to be closed. Pizza hut numbers should be printed in increasing order. Pizza huts are numbered from 1 to N in the order they are given in the input file.

Example(s)
sample input
sample output
2 1
0 0 1
1 0 1
2
1 2

sample input
sample output
3 2
0 0 1
1 0 1
10 3 1
0

sample input
sample output
3 2
0 0 100
13 17 5
10 10 10
1
2

<|response|>
## 1) Abridged problem statement (concise)

There are **N** pizza huts at integer coordinates \((x_i, y_i)\). Hut \(i\) can reach any point within **Manhattan distance** \(w_i\) in 10 minutes, i.e.
\[
|x-x_i| + |y-y_i| \le w_i.
\]
A hut \(A\) **can be closed** if **at least K other huts** can reach \(A\) in 10 minutes.

Output how many huts can be closed and their (1-based) indices in increasing order.

Constraints: \(2 \le N \le 10^5\), \(1 \le K \le N-1\), values up to \(10^9\).

---

## 2) Key observations

1. **Manhattan ball is a diamond**  
   The reachable area \(|x-x_i|+|y-y_i|\le w_i\) is a diamond in \((x,y)\).

2. **45° transform turns diamonds into axis-aligned rectangles**  
   Define:
   \[
   u = x + y,\quad v = x - y.
   \]
   Then:
   \[
   |x-x_i|+|y-y_i|\le w_i
   \iff
   \begin{cases}
   |u-u_i| \le w_i\\
   |v-v_i| \le w_i
   \end{cases}
   \]
   So hut \(i\) covers the rectangle:
   \[
   u \in [u_i-w_i,\, u_i+w_i],\quad v \in [v_i-w_i,\, v_i+w_i].
   \]

3. **Problem becomes point-in-rectangle counting**
   For each hut center \((u_i,v_i)\), count how many rectangles (from all huts) contain it.
   Hut \(i\) is closable iff:
   \[
   \text{count}(u_i,v_i) - 1 \ge K
   \]
   (subtract 1 to exclude its own rectangle).

4. **Efficient counting via sweep line + Fenwick tree**
   - Sweep over \(u\).
   - Maintain active rectangles (those whose \(u\)-interval contains current \(u\)).
   - For active rectangles, we need to count coverage at specific \(v\) points.

5. **Use range-add / point-query on \(v\) with BIT using difference trick**
   When a rectangle is active, it adds +1 to all \(v \in [L,R]\).
   Using a difference array:
   - add +1 at \(L\)
   - add -1 at \(R+1\)
   Then the coverage at a point \(v\) is prefix sum up to \(v\).

6. **Coordinate compression needed for \(v\)**
   \(v\) can be large/negative, so compress all \(v\)-values used:
   - \(v_i-w_i\)
   - \(v_i+w_i+1\) (for \(R+1\))
   - \(v_i\) (query)

---

## 3) Full solution approach

### Step A: Transform coordinates
For each hut \(i\):
- \(u_i = x_i + y_i\)
- \(v_i = x_i - y_i\)

Rectangle in \((u,v)\):
- \(u \in [u_i-w_i, u_i+w_i]\)
- \(v \in [v_i-w_i, v_i+w_i]\)

### Step B: Build sweep events over \(u\)
For each hut \(i\), create three events:
1. **Activate** at \(u = u_i-w_i\): add +1 coverage on \(v \in [v_i-w_i, v_i+w_i]\)
2. **Deactivate** at \(u = u_i+w_i+1\): add -1 coverage on same \(v\)-interval  
   (using \(+1\) makes the end exclusive, simplifying tie handling)
3. **Query** at \(u = u_i\): ask how many active rectangles cover \(v=v_i\)

Sort events by:
- increasing \(u\)
- for equal \(u\): process **updates before queries**  
  (so rectangles starting at \(u\) are counted; rectangles ending at \(u\) were already removed by using \(u_\text{max}+1\)).

### Step C: Fenwick tree on compressed \(v\)
We need:
- **range add** on \([L,R]\)
- **point query** at \(v_i\)

Using difference trick with BIT:
- To add \(\Delta\) on \([L,R]\), do:
  - BIT.add(L, +Δ)
  - BIT.add(R+1, -Δ)  
  Here we directly store \(R+1\) as \(v_i+w_i+1\) during compression.

Query at \(v_i\) = BIT.prefix_sum(idx(v_i)).

### Step D: Determine closable huts
Let `cnt[i]` be how many rectangles cover hut \(i\)’s center.
Closable iff `cnt[i] - 1 >= K`.

Complexity:
- Coordinate compression: \(O(N\log N)\)
- Sorting events (3N): \(O(N\log N)\)
- BIT operations: \(O(N\log N)\)
- Memory: \(O(N)\)

---

## 4) C++ implementation (detailed comments)

```cpp
#include <bits/stdc++.h>
using namespace std;

/*
  Fenwick (BIT) for prefix sums.
  We'll use it to store a "difference array" over compressed v-coordinates:
    range add [L, R] by delta  <=>  diff[L] += delta, diff[R+1] -= delta
  Then the value at point p is prefixSum(p).
*/
template<typename T>
struct Fenwick {
    int n;
    vector<T> bit; // 1-indexed

    void init(int n_) {
        n = n_;
        bit.assign(n + 1, 0);
    }

    void add(int idx, T delta) {
        for (; idx <= n; idx += idx & -idx) bit[idx] += delta;
    }

    T sumPrefix(int idx) const {
        T s = 0;
        for (; idx > 0; idx -= idx & -idx) s += bit[idx];
        return s;
    }
};

struct Event {
    long long u;   // sweep coordinate
    int type;      // 0 = update, 1 = query (updates must be processed first)
    int idx;       // hut index
    int delta;     // +1 or -1 for update; unused for query
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K;

    vector<long long> x(N), y(N), w(N);
    for (int i = 0; i < N; i++) cin >> x[i] >> y[i] >> w[i];

    // Transform to (u, v)
    vector<long long> u(N), v(N);
    for (int i = 0; i < N; i++) {
        u[i] = x[i] + y[i];
        v[i] = x[i] - y[i];
    }

    // Collect v-coordinates for compression:
    //  - interval start: v-w
    //  - interval end+1: v+w+1   (needed for diff trick)
    //  - query point: v
    vector<long long> allV;
    allV.reserve(3LL * N);
    for (int i = 0; i < N; i++) {
        allV.push_back(v[i] - w[i]);
        allV.push_back(v[i] + w[i] + 1);
        allV.push_back(v[i]);
    }
    sort(allV.begin(), allV.end());
    allV.erase(unique(allV.begin(), allV.end()), allV.end());

    auto compress = [&](long long val) -> int {
        // returns 1-based index
        return int(lower_bound(allV.begin(), allV.end(), val) - allV.begin()) + 1;
    };

    // Build sweep events: 2 updates + 1 query per hut
    vector<Event> events;
    events.reserve(3LL * N);
    for (int i = 0; i < N; i++) {
        // Activate at u-w with +1
        events.push_back({u[i] - w[i], 0, i, +1});
        // Deactivate at u+w+1 with -1 (end is exclusive)
        events.push_back({u[i] + w[i] + 1, 0, i, -1});
        // Query at u (center point)
        events.push_back({u[i], 1, i, 0});
    }

    sort(events.begin(), events.end(), [](const Event& a, const Event& b) {
        if (a.u != b.u) return a.u < b.u;
        return a.type < b.type; // updates (0) before queries (1)
    });

    Fenwick<int> fw;
    fw.init((int)allV.size());

    vector<int> cnt(N, 0);

    // Sweep: apply updates, answer queries
    for (const auto &e : events) {
        if (e.type == 0) {
            // Update event: add e.delta on v interval [v-w, v+w]
            // via diff trick: +delta at (v-w), -delta at (v+w+1)
            int L = compress(v[e.idx] - w[e.idx]);
            int Rplus1 = compress(v[e.idx] + w[e.idx] + 1);
            fw.add(L, e.delta);
            fw.add(Rplus1, -e.delta);
        } else {
            // Query event: how many active rectangles cover v[idx]?
            int p = compress(v[e.idx]);
            cnt[e.idx] = fw.sumPrefix(p);
        }
    }

    // Determine which huts are closable: cnt[i]-1 >= K
    vector<int> ans;
    for (int i = 0; i < N; i++) {
        if (cnt[i] - 1 >= K) ans.push_back(i + 1); // 1-based
    }

    cout << ans.size() << "\n";
    for (int i = 0; i < (int)ans.size(); i++) {
        if (i) cout << " ";
        cout << ans[i];
    }
    cout << "\n";

    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys
from bisect import bisect_left

# Fenwick tree (BIT) for prefix sums (1-indexed).
# We'll store a "difference array" in it:
#   range add [L, R] by delta => add(delta) at L, add(-delta) at R+1
# Then coverage at point p is prefix_sum(p).
class Fenwick:
    def __init__(self, n: int):
        self.n = n
        self.bit = [0] * (n + 1)

    def add(self, i: int, delta: int) -> None:
        while i <= self.n:
            self.bit[i] += delta
            i += i & -i

    def sum_prefix(self, i: int) -> int:
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s


def solve() -> None:
    data = sys.stdin.buffer.read().split()
    it = iter(data)

    n = int(next(it))
    k = int(next(it))

    x = [0] * n
    y = [0] * n
    w = [0] * n
    for i in range(n):
        x[i] = int(next(it))
        y[i] = int(next(it))
        w[i] = int(next(it))

    # Transform to (u, v) = (x+y, x-y)
    u = [0] * n
    v = [0] * n
    for i in range(n):
        u[i] = x[i] + y[i]
        v[i] = x[i] - y[i]

    # Coordinate compression for all v values used:
    # v-w, v+w+1, v
    coords = []
    coords.reserve(3 * n) if hasattr(coords, "reserve") else None  # harmless if absent
    for i in range(n):
        coords.append(v[i] - w[i])
        coords.append(v[i] + w[i] + 1)
        coords.append(v[i])
    coords = sorted(set(coords))

    def comp(val: int) -> int:
        # 1-based index
        return bisect_left(coords, val) + 1

    # Build events:
    # (u_position, type, idx, delta)
    # type: 0=update, 1=query; updates must come first for same u
    events = []
    for i in range(n):
        events.append((u[i] - w[i], 0, i, +1))        # activate
        events.append((u[i] + w[i] + 1, 0, i, -1))    # deactivate (exclusive end)
        events.append((u[i], 1, i, 0))                # query at center

    events.sort()  # sorts by u, then type (0 before 1), then idx...

    fw = Fenwick(len(coords))
    cnt = [0] * n

    for upos, typ, idx, delta in events:
        if typ == 0:
            # range add on v in [v-w, v+w] using diff trick
            L = comp(v[idx] - w[idx])
            Rplus1 = comp(v[idx] + w[idx] + 1)
            fw.add(L, delta)
            fw.add(Rplus1, -delta)
        else:
            # point query at v[idx]
            cnt[idx] = fw.sum_prefix(comp(v[idx]))

    # Closable if at least K other huts can reach it => cnt[i]-1 >= k
    res = [str(i + 1) for i in range(n) if cnt[i] - 1 >= k]

    sys.stdout.write(str(len(res)) + "\n")
    sys.stdout.write((" ".join(res)) + "\n")


if __name__ == "__main__":
    solve()
```

These implementations follow the same core idea: rotate/transform Manhattan balls into rectangles, sweep in one dimension, and maintain interval coverage in the other dimension with a Fenwick tree.