<|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 0 < dl + 1000c \le dvT
\Rightarrow 1 \le dl + 1000c \le dvT
\]
So:
- Lower: `1000c ≥ -dl + 1`
- Upper: `1000c ≤ dv*T - dl`

Thus:
\[
c \in \left[\left\lceil\frac{-dl+1}{1000}\right\rceil,\ \left\lfloor\frac{dvT-dl}{1000}\right\rfloor\right]
\]

#### Case 2: `dv < 0`
Multiplying flips inequalities:
\[
0 < \frac{dl + 1000c}{dv} \le T
\Rightarrow dvT \le dl + 1000c < 0
\]
Since `dl + 1000c` is integer, `< 0` is the same as `≤ -1`:
\[
dvT \le dl + 1000c \le -1
\]
So:
- Lower: `1000c ≥ dv*T - dl`
- Upper: `1000c ≤ -dl - 1`

Thus:
\[
c \in \left[\left\lceil\frac{dvT-dl}{1000}\right\rceil,\ \left\lfloor\frac{-dl-1}{1000}\right\rfloor\right]
\]

Finally, the number of integers in `[clow, chigh]` is:
- `max(0, chigh - clow + 1)`

### 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 (detailed comments)

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

static const int C = 1000; // circle length

// ceil(val / 1000) for possibly negative val, with integer arithmetic.
// Returns smallest integer c such that 1000*c >= val.
static long long ceil_div_1000(long long val) {
    if (val >= 0) {
        return (val + C - 1) / C;
    }
    // For negative values: ceil(val/C) = -floor((-val)/C)
    // But C++ division truncates toward 0, so we implement carefully:
    // Example: val=-1 => ceil(-0.001)=0.
    return -((-val) / C);
}

// floor(val / 1000) for possibly negative val, with integer arithmetic.
// Returns largest integer c such that 1000*c <= val.
static long long floor_div_1000(long long val) {
    if (val >= 0) {
        return val / C;
    }
    // For negative values:
    // Example: val=-1 => floor(-0.001) = -1.
    return -(((-val) + C - 1) / C);
}

// Count number of meeting times between (l1,v1) and (l2,v2) within (0, T].
static long long count_meetings(int l1, int v1, int l2, int v2, int T) {
    // Meetings are defined only when directions are opposite.
    // Same sign means both clockwise or both counter-clockwise => no "meet".
    if ((v1 > 0) == (v2 > 0)) return 0;

    long long dv = (long long)v1 - (long long)v2;
    long long dl = (long long)l2 - (long long)l1;

    long long c_low, c_high;

    if (dv > 0) {
        // Need: 1 <= dl + 1000*c <= dv*T
        c_low  = ceil_div_1000(-dl + 1);
        c_high = floor_div_1000(dv * T - dl);
    } else { // dv < 0
        // Need: 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;
}

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

    int N, T;
    cin >> N >> T;

    vector<int> L(N), V(N);
    for (int i = 0; i < N; i++) cin >> L[i];
    for (int i = 0; i < N; i++) cin >> V[i];

    // ans[i] counts how many questions soldier i asks.
    // We iterate ordered pairs (i, j), i != j. Each meeting contributes 1 to ans[i].
    vector<long long> ans(N, 0);

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (i == j) continue;
            ans[i] += count_meetings(L[i], V[i], L[j], V[j], T);
        }
    }

    for (int i = 0; i < N; i++) {
        if (i) cout << ' ';
        cout << ans[i];
    }
    cout << "\n";
    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()
```

