---
# System prepended metadata

title: JOIG 23/24 Infection Simulation
tags: [statement]

---

# JOIG 23/24 Infection Simulation

https://www.acmicpc.net/problem/31641

Yesterday, $N$ customers visited the EGOI cafeteria. Each customer is assigned a number from $1$ to $N$. The arrival and departure times of customer $i$ are $L_i$ and $R_i$, respectively. It was revealed today that one of these customers was infected with a new infectious disease $X$ during their visit.

The infectiousness of disease $X$ is represented by an integer $x$. Specifically, for $1 \leq i \leq N$, customer $i$ becomes infected if they spend a cumulative time of $x$ or more in the cafeteria with one or more infected customers (the sum of $x$ can be spread across several infected customers).

Since strict infection control measures are in place in the JOI country, it's necessary to accurately determine the number of infected individuals. However, the specific individual who was initially infected, as well as the value of $x$ representing the infectiousness, is unknown.

To address this, Rie, the manager of the EGOI cafeteria, wants to determine the number of customers who will ultimately become infected for each of $Q$ scenarios. In scenario $j$ (where $1 \leq j \leq Q$), the initial infected customer is $P_j$, and the infectiousness of disease $X$ is $X_j$.

Given the customers' visit information and the scenarios, create a program that outputs the final number of infected customers for each scenario. Note that if a customer gets infected exactly at the time of their departure, they are counted as infected. Also, once a customer is infected with disease $X$, they remain infected permanently.

## Input Format

The input is given in the following format:


```
N
L1 R1
L2 R2
...
LN RN
Q
P1 X1
P2 X2
...
PQ XQ
```

## Output Format

Output $Q$ lines. The $j$-th line (where $1 \leq j \leq Q$) contains the final number of infected customers for the $j$-th scenario.

## Constraints

* $1 \leq N \leq 100,000$
* $0 \leq L_i < R_i \leq 10^9$ (for $1 \leq i \leq N$)
* $1 \leq Q \leq 100,000$
* $1 \leq P_j \leq N$ (for $1 \leq j \leq Q$)
* $1 \leq X_j \leq 10^9$ (for $1 \leq j \leq Q$)
* All input values are integers.

## Subtasks

![image](https://hackmd.io/_uploads/H1P7Me3SR.png)

Subtask 9: The minimum value of $R_i - L_i$ (for $1 \leq i \leq N$) is greater than or equal to the maximum value of $X_j$ (for $1 \leq j \leq Q$).

## Example Inputs and Outputs
Example Input 1

    4
    10 40
    20 80
    45 60
    70 95
    1
    1 15

Example Output 1

`3`

Example Input 2

    8
    0 30
    0 90
    0 80
    0 60
    0 20
    0 40
    0 70
    0 50
    3
    1 30
    1 40
    4 50

Example Output 2

    7
    1
    5

Example Input 3

    5
    0 10
    0 10
    0 10
    0 10
    0 10
    4
    1 9
    1 10
    1 11
    1 1000000000

Example Output 3

    5
    5
    1
    1

Example Input 4

    7
    38 61
    13 27
    10 54
    22 56
    49 75
    27 47
    70 99
    1
    3 10

Example Output 4

`6`

Example Input 5

    10
    10 20
    11 21
    13 23
    16 26
    20 30
    25 35
    31 41
    38 48
    46 56
    80 90
    4
    1 3
    1 6
    1 8
    1 10

Example Output 5

    8
    5
    3
    1

Example Input 6

    7
    10 54
    38 61
    13 27
    22 56
    49 75
    27 47
    70 99
    5
    1 3
    1 6
    1 9
    1 12
    1 15

Example Output 6

    7
    6
    6
    6
    4

Example Input 7

    7
    38 61
    13 27
    10 54
    22 56
    49 75
    27 47
    70 99
    5
    1 10
    2 10
    3 10
    4 10
    5 10

Example Output 7

    4
    6
    6
    5
    2