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种任务。

时间/ms	任务类型编号	显卡0任务数	显卡0的等待队列	显卡0的响应时间/ms	显卡1任务数	显卡1的等待队列	显卡1的响应时间/ms	选择哪个显卡？
0	1	0	空	0	0	空	0	0号显卡
12	0	1	[54ms],首个任务已运行12ms	54-12=42	0	空	0	1号显卡
38	0	1	[54ms],首个任务已运行38ms	54-38=16	1	空	0	1号显卡
39	2	1	[54ms],首个任务已运行39ms	54-39=15	2	[23ms],首个任务已运行1ms	22	0号显卡
204	1	1	空	0	2	空	0	0号显卡

数据范围及约定

对于\(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?