题目大意

这道题目要求我们模拟一个DNS本地缓存系统

思路

1.缓存容量：缓存最多能存储N条记录。

2.URL请求处理： 每秒处理一个URL请求。 如果请求的URL已经存在于缓存中，直接返回from_cache（输出0）。

题目内容

小明是一名软件工程师，他正在开发一个DNS本地缓存系统。在互联网中，DNS（Domain Name System）用于将域名（例如www.example.com）解析为IP地址，以便将请求发送到正确的服务器上。通常情况下，DNS请求会发送到互联网上的某个DNS服务器，这会造成一定的网络延迟和负载。为了解决这个问题，小明想要开发一个本地DNS缓存系统，可以在本地缓存一部分DNS请求的结果，以提高性能和减轻网络负载。

小明的这个DNS本地缓存系统有功能如下：

1. 系统初始状态无存储记录，最大可缓存N条记录;
2. 系统每1秒能解析1个URL地址，先从本地DNS上查找，如果本地缓存中能查到就直接返回from_cache;
3. 如果本地DNS.上没有该地址，返回from_internet, 并从URL的属性列表tls上，读取该URL的TTL(Time To Live代表该URL的生存时长，即能够保存到缓存系统中的时长)，并将URL存入缓存系统中;如果在ts上未能读到该URL的TTL,设置默认TTL为5s;
4. 本地缓存系统中URL地址的TTL每秒减1，当TTL=0时，将该URL地址从缓存系统中移除;
5. 在系统空间装满后，如果还有新的URL要录入，则将TTL最小的一个URL移除，如果TTL最小的URL存在多个，按照先进先出的方式移除1个URL.

现在每1秒输入一个URL地址,求每个URL地址的解析方式(from_cache 还是 from_internet)。

输入描述

第一行两个整数$N\ X$ ， 代表DNS的缓存空间以及待请求的URL的数量

接下来一行$X$个整数，分别代表对应的$url$ , 形如: $url_1 ,url_2 , url_3 , ... ,url_X$ , 元素允许重复

接下来一行整数 $Y$ , 代表URL的属性列表tls长度.

接下来$Y$行，每行两个整数，$url_i$ 和 $ttl_i$ .

数据范围说明:

$0 < N, X, Y \leq 65535，N, X，Y为正整数$

$0 \leq url_i, ttl_i \leq 65535, url_i, ttl_i为整数$

输出描述

每秒中url的解析方式列表(0: from_cache, 1: from_internet)

样例1

输入

5 5
3 1 2 1 2
2
1 4
2 2

输出

1 1 1 0 1

样例2

输入

10 15
11 14 10 5 8 3 8 13 12 9 12 15 15 7 7
8
11 2
14 11
10 9
5 7
8 1
13 10
9 10
15 8

输出

1 1 1 1 1 1 1 1 1 1 0 1 0 1 0