<|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

```cpp
#include <bits/stdc++.h>
// #include <coding_library/data_structures/fenwick.hpp>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

template<class T>
class Fenwick {
  private:
    int sz, log_size;
    vector<T> tr;

  public:
    void init(int n) {
        sz = n + 1;
        log_size = 31 - __builtin_clz(sz);
        tr.assign(sz + 1, 0);
    }

    void update(int idx, T val) {
        if(idx <= 0) {
            assert(false);
            return;
        }
        for(; idx <= sz; idx += (idx & -idx)) {
            tr[idx] += val;
        }
    }

    T query(int idx) {
        T ans = 0;
        for(; idx >= 1; idx -= (idx & -idx)) {
            ans += tr[idx];
        }

        return ans;
    }

    T query(int l, int r) { return query(r) - query(l - 1); }

    int find_kth(T k) {
        int idx = 0;
        for(int i = log_size; i >= 0; i--) {
            if(idx + (1 << i) < sz && tr[idx + (1 << i)] < k) {
                k -= tr[idx + (1 << i)];
                idx += (1 << i);
            }
        }
        return idx + 1;
    }
};

int n, k;
vector<int64_t> x, y, w;

void read() {
    cin >> n >> k;
    x.resize(n);
    y.resize(n);
    w.resize(n);
    for(int i = 0; i < n; i++) {
        cin >> x[i] >> y[i] >> w[i];
    }
}

void solve() {
    // We will start with the standard trick of rotating everything by 45%
    // degrees and scaling by two with (x, y) goes into (x + y, x - y). The area
    // of each pizza hut is now a rectangle with corners (x - w, y - w) and (x +
    // w, y + w), where this is the transformed (x, y). We want to figure out
    // which centers are covered by at least K rectangles (excluding the given
    // one). This can be done by treating each rectangle as two events (low_y,
    // high_y, low_x, +1), and (low_y, high_y, high_x, -1), and maintaining a
    // segment or fenwick tree over the Ys. We will add +delta at low_y and
    // subtract it at (high_y+1). Then we will also have each center as a query,
    // and we can simply query the fenwick tree. For convenince, we can compress
    // all Y coordinates before processing the events.

    vector<int64_t> tx(n), ty(n);
    for(int i = 0; i < n; i++) {
        tx[i] = x[i] + y[i];
        ty[i] = x[i] - y[i];
    }

    vector<int64_t> all_ys;
    for(int i = 0; i < n; i++) {
        all_ys.push_back(ty[i] - w[i]);
        all_ys.push_back(ty[i] + w[i] + 1);
        all_ys.push_back(ty[i]);
    }
    sort(all_ys.begin(), all_ys.end());
    all_ys.erase(unique(all_ys.begin(), all_ys.end()), all_ys.end());

    auto compress = [&](int64_t v) -> int {
        return lower_bound(all_ys.begin(), all_ys.end(), v) - all_ys.begin() +
               1;
    };

    struct Event {
        int64_t x_coord;
        int type;
        int idx;
        int delta;
    };

    vector<Event> events;
    for(int i = 0; i < n; i++) {
        events.push_back({tx[i] - w[i], 0, i, 1});
        events.push_back({tx[i] + w[i] + 1, 0, i, -1});
        events.push_back({tx[i], 1, i, 0});
    }

    sort(events.begin(), events.end(), [](const Event& a, const Event& b) {
        if(a.x_coord != b.x_coord) {
            return a.x_coord < b.x_coord;
        }
        return a.type < b.type;
    });

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

    vector<int> cnt(n);
    for(auto& e: events) {
        if(e.type == 0) {
            int lo = compress(ty[e.idx] - w[e.idx]);
            int hi = compress(ty[e.idx] + w[e.idx] + 1);
            fw.update(lo, e.delta);
            fw.update(hi, -e.delta);
        } else {
            cnt[e.idx] = fw.query(compress(ty[e.idx]));
        }
    }

    vector<int> result;
    for(int i = 0; i < n; i++) {
        if(cnt[i] - 1 >= k) {
            result.push_back(i + 1);
        }
    }

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

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    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.
