背景

  堆鲁诺·堆巴拿，是一名扬哥's-star。它第一天来到实验室，就引起了一阵 rua 堆堆热潮。

  但是，由于义父义母们太过热情，堆堆难免会感到厌烦，并适时进行攻击性行为。

题目描述

这里，我们简单把情况假设为有 $n$ 人 rua 了堆堆，而每人 rua 后积累 $a[i]$ 的厌烦度，而每当堆堆的厌烦度积累到 m 时就会发起进攻，每次攻击后清空厌烦度（下一人从 0 开始）。

这里我们定义另一种扬哥在场的情况，这种情况下，堆堆攻击后会被扬哥揍，导致后期积累厌烦度的上限上升 20%（整数默认取整）。

接下来，我们模拟这一情况，请你给出被攻击的人的下标。

Format

Input

  第一行给定两个整数 $n$ 和 $m$，代表有 $n$ 人 rua 了堆堆，堆堆初始厌烦度上限为 $m$。   第二行依次读入 $n$ 个 整数 $a[i]$，依次代表第 1 至第 $n$ 人 rua 堆堆后堆堆增长的厌烦值。   第三行读入 $o$，表示扬哥有 $o$ 个时间段在场。   其后 $o$ 行，每行有 $t[i$] 和 $y[i]$， 代表扬哥在第 $t[i]$ 人至第 $y[i]$ 人 rua 堆堆期间在场。

Output

若干整数，即被攻击者的序号，末尾有空格。

Samples

8 42
36 18 12 8 40 37 11 36
1
1 7

2 5 8

Limitation

1s, 1024KiB for each test case. $n \leq 10000, m \leq 50000, o \leq 10.$

题中所有整数 int 足矣。