Problem 3E: K8s - Easy Version

时间限制：2000ms

空间限制：512MB

题目描述

电自院最近新设立了一台AI推理服务器，旨在预测校内各楼宇的耗电量。尽管这台AI服务器上装有多张显卡，但是由于负责该项目的同学，小F，并不会任何的后端技术，导致现在这台服务器只能串行处理请求，无法利用这么多显卡。由于小F的导师对这台服务器的QPS如此之低感到不满，一些改进方案被提了出来：

AI服务器上现有$n$个显卡，依次编号为$0,1,2,...,n-1$，编号为$i$的显卡算力为$c_i$。为充分利用这些显卡，小F为每个显卡都创建了一个Pod，每个Pod中都运行着调用某块显卡进行AI推理的程序。由于每个Pod中的显卡型号可能有差别，且任务的种类繁多，因此不同任务在不同Pod中的运行时间会有差异。经过研究统计，小F发现，AI服务器会收到$m$种推理任务，编号为$0,1,2,...,m-1$，类型编号为$i$的任务的规模为$a_i$。当类型编号为$i$的任务在编号为$j$的显卡上运行时，所需要的时间为$[a_i/c_j]$毫秒。这里符号$[x]$表示不大于$x$的最大整数。

为了合理的将推理任务分配给Pod，小F设计了一种分配机制。每当AI服务器收到一个推理任务时，就会把这个任务分配给**响应用时最短**的Pod；如果有多个Pod的响应用时均最短，那么分配给**完成任务的数量(含正在运行的任务)最少**的Pod；如果有多个Pod的响应用时均最短且完成任务数量一致，那么分配给**编号最小**的那个Pod。

某时刻一个任务在某个Pod上的“响应用时”的定义为：将这一任务加入该Pod后，该Pod**开始**这一任务的时刻与当前时刻的时间差。例如，一个Pod正在运行一个需要10毫秒的任务，当前该任务已经运行了5毫秒，而且恰好还有3个用时分别为12毫秒、31毫秒和8毫秒的任务等待在该Pod上运行，如果有一个此时有一个新任务可能会分配到该Pod上，那么当前时刻这个新任务在该Pod上的响应时间就是$(10-5)+(12+31+8)=56$毫秒。

现在，AI服务器收到了$q$个推理任务，第$i$个推理任务的到达服务器的时刻为$t_i$毫秒，类型编号为$k_i$。这里保证所有$t_i$严格递增，即对于$\forall i\in\{1,2,...,q-1\}, t_i< t_{i+1}$。小F希望知道，按照上述方案，这些推理任务都会被分配给哪个Pod。

由于小F的代码水平稀烂，因此他无法完成这项工作。因此，他现在求助于你，希望你能帮他完成这个程序。

输入格式

第1行，包含3个整数$n,m,q$；

第2行，包含$n$个整数，分别表示$c_0,c_1,c_2,...,c_{n-1}$；

第3行，包含$m$个整数，分别表示$a_0,a_1,a_2,...,a_{m-1}$；

第4~$(q+3)$行，每行2个整数，第$(3+i)$行的整数分别表示$t_i,k_i$，

一行内的多个整数之间使用1个空格分开，且每行的开头和末尾没有多余空格。

输出格式

输出$q$行，每行1个整数。第$i$行的整数表示服务器接收到的$i$个推理任务被分配到的Pod的显卡编号。

样例输入

2 3 5
6 8
190 328 112
0 1
12 0
38 0
39 2
204 1

样例输出

0
1
1
0
0

样例解释

本例中有2种显卡和3种任务。

数据范围及约定

对于$20\%$的数据，满足$n,q \le 100, m\le 10$

对于$60\%$的数据，满足$n,m,q \le 1000$；

对于$100\%$的数据，$1 \le n,q \le 2\times 10^5$，$1\le m \le 1000$，$0\le t_i\le 10^9$，$0 \le k_i < m$，$1\le c_i,a_i\le 10^9$，所有输入数值均为非负整数。

提示

猜猜这题为什么叫K8s?