연산 추가하기

FuriosaAI는 데이터센터 및 고성능 엣지를 위한 AI 반도체를 개발한다. 2세대 제품 RNGD는 자체 설계한 아키텍처인 TCP(Tensor Contraction Processor) 기반의 인공지능 가속기로, PyTorch 등 주요 프레임워크와 호환되는 SDK를 제공한다.

RNGD에서 인공지능 모델의 추론을 수행하려면, 먼저 모델에서 수행하는 계산을 RNGD 명령어들의 나열로 변환하는, 즉 컴파일하는 과정이 필요하다. 실제 컴파일 과정을 단순화한 다음과 같은 상황을 가정해보자.

RNGD 연산 시간의 기본 단위는 사이클로, 모델의 실행은 총 $H$ 사이클 이내에 끝나야 한다는 제한이 있다. $H$개의 사이클을 순서대로 사이클 $1$, 사이클 $2$, $\cdots$, 사이클 $H$라고 부르자.

컴파일된 인공지능 모델에는 총 $N$개의 연산이 있으며, 이 중 $i$번째 연산은 사이클 $A\_i$부터 사이클 $B\_i$까지 실행된다. 실행되는 사이클이 서로 겹치는 연산들이 있을 수도 있다.

RNGD에서 컴파일된 모델을 실행하는 도중에 추가 연산 하나를 함께 수행해야 한다는 요청이 들어왔다. 이때 추가 연산은 기존 $N$개의 연산 중 어느 것과도 실행 사이클이 겹치면 안 되며, $H$ 사이클 이내에서 수행이 완료되어야 한다. 구체적으로,

• 추가 연산을 수행하는 데 $T$ 사이클이 걸린다고 하자. 즉, 추가 연산이 사이클 $S$에 시작된다면, 사이클 $S+T-1$에 종료된다.
• 추가 연산이 수행되는 $T$개의 사이클 동안, 다른 연산이 동시에 수행되어서는 안 된다.
• $1\leq S\leq S+T-1\leq H$여야 한다.

추가 연산의 종류에 따라 소요되는 사이클 수 $T$가 달라질 수 있으므로, $Q$가지 시나리오를 미리 검토하려 한다. $i$번째 시나리오에서 추가 연산을 수행하는 데 $T\_i$ 사이클이 필요한 경우, 조건을 만족하는 시작 사이클 $S$가 총 몇 개인지 빠르게 계산해보자.

각 시나리오의 추가 연산은 누적되지 않음에 유의하라.

첫째 줄에 인공지능 모델을 구성하는 연산의 수 $N$, 전체 사이클 수 $H$가 공백으로 구분되어 주어진다. ($0 \leq N \leq 200\\,000$; $1 \leq H \leq {10}^9$)

이후 $N$개의 줄에 걸쳐, 그 중 $i$번째 줄에 $i$번째 연산이 실행되는 시작 사이클과 종료 사이클을 가리키는 두 정수 $A\_i, B\_i$가 공백으로 구분되어 주어진다. ($1 \leq A\_i \leq B\_i \leq H$)

그 다음 줄에 시나리오의 개수 $Q$가 주어진다. ($1 \leq Q \leq 200\\,000$)

이후 $Q$개의 줄에 걸쳐, 추가 연산의 소요 사이클 수 $T\_i$가 주어진다. ($1 \leq T\_i \leq H$)

$Q$개의 줄에 각 시나리오에 대한 정답을 순서대로 출력한다.