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

188. Factory guard
time limit per test: 0.25 sec.
memory limit per test: 4096 KB
input: standard input
output: standard output



The fence around the strategically important Berland pistachio factory has a circle form. N soldiers were posted to guard the factory according to the new government program "Pistachio protection in industry and life" (decree 1731 of 10/10/2003). Each soldier moves along the outer side of the fence at a constant speed (clockwise or counter-clockwise). The fence perimeter is 1000 meters long. The initial position of each soldier Li (the distance from the entrance checkpoint round the circle clockwise) is known, 0<=Li<=999, all Li are different integers. The speed of each soldier is Vi meters per minute (-100<=Vi<=100, Vi<>0, Vi is integer). Note: if a soldier's speed is negative, then he moves in the counter-clockwise direction, and in the clockwise direction in the opposite case.
If a soldier meets another soldier on his way, he immediately asks him a password "Have you a spare cigarette?", and getting a "No" answer he keeps on moving. Note, the term "meet" means the moment of time, when the two soldiers are at one and the same point with the opposite velocities. Since the soldiers serve for over a year they have learned to say the password and the answer so quickly, that if a soldier meets several soldiers at once, he manages both to ask each soldier for a password and to answer him.
Your task is to find out how many times each soldier asks a password during the period of T minutes from the initial moment of time (inclusive).

Input
The first line contains two natural numbers N and T (1<=N<=20; 1<=T<=50). The second line contains integer numbers L1, L2, ..., LN, and the third line contains V1, V2, ..., VN. Numbers in each line are separated by one or more spaces.

Output
Output N numbers B1, B2, ..., BN separated by a space, where Bi is the number of questions asked by the i-th soldier.

Sample test(s)

Input
3 2
0 1 2
1 -1 -2

Output
2 1 1
Author:	Michael R. Mirzayanov
Resource:	ACM International Collegiate Programming Contest 2003-2004
North-Eastern European Region, Southern Subregion
Date:	2003 October, 9

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

There are **N ≤ 20** soldiers on a **circular fence of length 1000** meters. Soldier *i* starts at integer position **Li** (0…999, all distinct) and moves at constant integer speed **Vi** (nonzero; **Vi > 0** clockwise, **Vi < 0** counter-clockwise).

During the next **T ≤ 50** minutes, whenever **two soldiers are at the same point at the same time AND move in opposite directions**, they "meet", and **each asks the other one question**. If multiple soldiers meet at once, all relevant pairs count.

Output **Bi** = number of questions asked by soldier *i* during time interval **(0, T]** (time 0 included in statement, but since all Li are distinct there is no meeting at t=0).

---

## 2) Key observations

1. **Only opposite directions matter**
   A "meet" is defined only if velocities are opposite in direction.
   So if `Vi` and `Vj` have the same sign ⇒ they contribute **0**.

2. **Unwrap the circle into an infinite line (standard trick)**
   On the circle, positions are modulo 1000. Two positions are identical on the circle if they differ by `1000*k`.
   So we can consider infinite "copies" of each soldier at starting positions:
   \[
   x_i^{(c)}(t)=L_i + 1000c + V_i t,\quad c\in\mathbb{Z}
   \]
   Then a meeting on the circle becomes an intersection between the line of soldier `i` and **some copy** of soldier `j`.

3. **Meetings reduce to counting integers in an interval**
   For a pair (i, j), meeting times satisfy:
   \[
   L_i + V_i t = L_j + 1000c + V_j t
   \Rightarrow (V_i - V_j)t = (L_j - L_i) + 1000c
   \]
   So:
   \[
   t = \frac{(L_j - L_i) + 1000c}{V_i - V_j}
   \]
   We need **0 < t ≤ T**, and we can count how many integers `c` make this true.

4. **Careful integer ceil/floor with negatives**
   We will compute bounds on `c` using:
   - `ceil(val/1000)` and `floor(val/1000)` for possibly negative `val`.

---

## 3) Full solution approach

### Step A: For each ordered pair (i, j), count meetings where i asks j
Because in each meeting **both** soldiers ask, we can compute for ordered pairs `(i, j)` with `i != j` and add the number of meetings to `ans[i]`.

### Step B: Counting meetings for a fixed ordered pair (i, j)
Let:
- `dv = Vi - Vj`
- `dl = Lj - Li`

Meeting condition (for some integer `c`):
\[
t = \frac{dl + 1000c}{dv}, \quad 0 < t \le T
\]

Also, if `Vi` and `Vj` have the same sign ⇒ return 0 immediately.

Now transform the time inequality into an inequality on the integer expression `dl + 1000c`. Because `dl` and `c` are integers, `dl + 1000c` is integer. The strict `t > 0` becomes a strict constraint that we can implement as `>= 1` or `<= -1` depending on the sign.

#### Case 1: `dv > 0`
\[
0 < \frac{dl + 1000c}{dv} \le T
\Rightarrow 1 \le dl + 1000c \le dvT
\]
So:
- Lower: `1000c ≥ -dl + 1`  (use first_c_geq)
- Upper: `1000c ≤ dv*T - dl` (use last_c_leq)

#### Case 2: `dv < 0`
Multiplying flips inequalities:
\[
0 < \frac{dl + 1000c}{dv} \le T
\Rightarrow dvT \le dl + 1000c \le -1
\]
So:
- Lower: `1000c ≥ dv*T - dl` (use first_c_geq)
- Upper: `1000c ≤ -dl - 1`   (use last_c_leq)

Finally, the number of integers in `[c_low, c_high]` is `max(0, c_high - c_low + 1)`.

Here `first_c_geq(val)` returns the smallest integer c with `1000c ≥ val` (i.e. `ceil(val/1000)`) and `last_c_leq(val)` returns the largest integer c with `1000c ≤ val` (i.e. `floor(val/1000)`), both implemented carefully for negative values.

### Step C: Complexity
We do O(1) work per ordered pair `(i, j)`:
- `N ≤ 20` ⇒ at most 400 ordered pairs ⇒ extremely fast.

---

## 4) C++ implementation

```cpp
#include <bits/stdc++.h>

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

int n, t;
vector<int> l, v;

void read() {
    cin >> n >> t;
    l.resize(n);
    v.resize(n);
    cin >> l >> v;
}

int64_t first_c_geq(int64_t val) {
    if(val >= 0) {
        return (val + 999) / 1000;
    }
    return -((-val) / 1000);
}

int64_t last_c_leq(int64_t val) {
    if(val >= 0) {
        return val / 1000;
    }
    return -((-val + 999) / 1000);
}

int64_t count_meetings(int l1, int v1, int l2, int v2) {
    if((v1 > 0) == (v2 > 0)) {
        return 0;
    }

    int64_t dv = v1 - v2;
    int64_t dl = l2 - l1;

    int64_t c_low, c_high;
    if(dv > 0) {
        c_low = first_c_geq(-dl + 1);
        c_high = last_c_leq(dv * t - dl);
    } else {
        c_low = first_c_geq(dv * t - dl);
        c_high = last_c_leq(-dl - 1);
    }

    if(c_high < c_low) {
        return 0;
    }
    return c_high - c_low + 1;
}

void solve() {
    // Instead of having a circle, we can think of this as a plane with lines y
    // = Vi * t + Li for each of the soldiers. We will simply just make an
    // infinite number of copies starting at Li, Li + 1000, Li + 2000 and so on
    // (also same for negatives). Let's figure out how many intersections there
    // would be between each pair of lines. We know the form of one line is y =
    // Vi * t + Li, while we can consider all the lines y = Vi * t + Li + 1000 *
    // c. Particularly, we can binary search on c to figure out the first t > 0
    // and the last integer t <= T, or alternatively just do some simple math.
    // The answer being the length of this interval. The time complexity will be
    // O(N^2).

    vector<int64_t> ans(n, 0);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(i != j) {
                ans[i] += count_meetings(l[i], v[i], l[j], v[j]);
            }
        }
    }
    for(int i = 0; i < n; i++) {
        cout << ans[i];
        if(i < n - 1) {
            cout << ' ';
        }
    }
    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();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys

C = 1000  # circle length

def ceil_div_1000(val: int) -> int:
    """
    Return ceil(val / 1000) for possibly negative val.
    Equivalent to smallest integer c such that 1000*c >= val.
    Python's // is floor division, so:
      ceil(a/b) = -((-a)//b) for b>0
    """
    return -((-val) // C)

def floor_div_1000(val: int) -> int:
    """
    Return floor(val / 1000) for possibly negative val.
    Equivalent to largest integer c such that 1000*c <= val.
    Python's // already does floor division.
    """
    return val // C

def count_meetings(l1: int, v1: int, l2: int, v2: int, T: int) -> int:
    """
    Count meetings between soldiers (l1,v1) and (l2,v2) during (0, T],
    where a meeting requires same position on the circle and opposite directions.
    """
    # Only opposite directions count as a "meet"
    if (v1 > 0) == (v2 > 0):
        return 0

    dv = v1 - v2
    dl = l2 - l1

    if dv > 0:
        # 1 <= dl + 1000*c <= dv*T
        c_low = ceil_div_1000(-dl + 1)
        c_high = floor_div_1000(dv * T - dl)
    else:
        # dv < 0:
        # dv*T <= dl + 1000*c <= -1
        c_low = ceil_div_1000(dv * T - dl)
        c_high = floor_div_1000(-dl - 1)

    if c_high < c_low:
        return 0
    return c_high - c_low + 1

def solve() -> None:
    data = sys.stdin.read().strip().split()
    N = int(data[0])
    T = int(data[1])

    L = list(map(int, data[2:2+N]))
    V = list(map(int, data[2+N:2+2*N]))

    ans = [0] * N

    # Ordered pairs: each meeting causes each soldier to ask once.
    for i in range(N):
        total = 0
        for j in range(N):
            if i == j:
                continue
            total += count_meetings(L[i], V[i], L[j], V[j], T)
        ans[i] = total

    sys.stdout.write(" ".join(map(str, ans)) + "\n")

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