小红经营着一家创意烘焙坊，店内共有 种编号为 的不同款式慕斯模具。在今天的生产流水线上，小红记录了 次模具的使用信息。第 次记录显示，在时间点 使用了编号为 的模具。 为了优化清洗流程，小红提出了 个查询。每个查询由一个起始时间 和一个固定的时间跨度 组成，代表观察的时间区间为 （闭区间）。对于每个查询，小红想知道在这个时间区间内，使用了多少种不同编号的模具。

输入描述:

第一行包含三个整数 （），分别表示模具的总数、查询的时间跨度长度以及查询的数量。 第二行包含 个整数 （），表示每个查询区间的起始时间。 第三行包含一个整数 （），表示模具的使用记录总数。 接下来的 行，每行包含两个整数 和 （），表示在时间 使用了编号为 的模具。

输出描述:

输出一行 个整数，每两个整数之间用空格分隔，依次对应每个查询区间内不同模具的种类数。