> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/binary-searching-and-sorting/chef-restaurant.md).

# Chef Restaurant

Chef is a cook and he has recently opened a restaurant.

The restaurant is open during NN time intervals \[L1,R1),\[L2,R2),…,\[LN,RN)\[L1,R1),\[L2,R2),…,\[LN,RN). No two of these intervals overlap — formally, for each valid ii, jj such that i≠ji≠j, either Ri\<LjRi\<Lj or Rj\<LiRj\<Li.

MM people (numbered 11 through MM) are planning to eat at the restaurant; let's denote the time when the ii-th person arrives by PiPi. If the restaurant is open at that time, this person does not have to wait, but if it is closed, this person will wait until it is open. Note that if this person arrives at an exact time when the restaurant is closing, they have to wait for the next opening time.

For each person, calculate how long they have to wait (possibly 00 time), or determine that they will wait forever for the restaurant to open.

#### Input <a href="#input" id="input"></a>

* The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
* The first line of the input contains two space-separated integers NN and MM.
* NN lines follow. For each valid ii, the ii-th of these lines contains two space-separated integers LiLi and RiRi.
* MM lines follow. For each valid ii, the ii-th of these lines contains a single integer PiPi.

#### Output <a href="#output" id="output"></a>

For each test case, print MM lines. For each valid ii, the ii-th of these lines should contain a single integer — the time person ii has to wait, or −1−1 if person ii has to wait forever.

#### Constraints <a href="#constraints" id="constraints"></a>

* 1≤T≤1001≤T≤100
* 1≤N,M≤1051≤N,M≤105
* 1≤Li\<Ri≤1091≤Li\<Ri≤109 for each valid ii
* 1≤Pi≤1091≤Pi≤109 for each valid ii
* the intervals are pairwise disjoint
* the sum of NN for all test cases does not exceed 3⋅1053⋅105
* the sum of MM for all test cases does not exceed 3⋅1053⋅105

#### Subtasks <a href="#subtasks" id="subtasks"></a>

**Subtask #1 (30 points):**

* the sum of NN for all test cases does not exceed 1,0001,000
* the sum of MM for all test cases does not exceed 1,0001,000

**Subtask #2 (70 points):** original constraints

#### Example Input <a href="#exampleinput" id="exampleinput"></a>

```
1
4 5
5 7
9 10
2 3
20 30
5
6
7
35
1
```

#### Example Output <a href="#exampleoutput" id="exampleoutput"></a>

```
0
0
2
-1
1
```

```java
class Codechef {
    // O(NlogN) + O(MlogN)
    public static int[] waitingTime(int[][] intervals, int[] customers) {
        // Sorting on start time
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        // Now just binary searching for customers
        int[] ans = new int[customers.length];
        for (int i = 0; i < ans.length; i++)
            ans[i] = findTime(intervals, customers[i]);
        return ans;
    }

    public static int findTime(int[][] intervals, int arrival) {
        if (arrival >= intervals[intervals.length - 1][1])
            return -1;
        int low = 0, high = intervals.length - 1;
        int ans = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arrival >= intervals[mid][0] && arrival < intervals[mid][1]) {
                ans = 0;
                break;
            } else if (arrival >= intervals[mid][1])
                low = mid + 1;
            else {
                // If the arrival time is just before this interval
                if (mid == low || intervals[mid - 1][1] <= arrival) {
                    ans = intervals[mid][0] - arrival;
                    break;
                }
                high = mid - 1;
            }
        }
        return ans;
    }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mayanktyagi3111.gitbook.io/interview-prep/binary-searching-and-sorting/chef-restaurant.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.