407745: GYM102889 F woafrnraetns 与正整数
Memory Limit:512 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
F. woafrnraetns 与正整数time limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output
woafrnraetns 喜欢正整数。他收集了一个由 n 个正整数组成的序列 a1, a2, ..., an,以及另外两个正整数 p 和 q (p < q)。
某天,woafrnraetns 开始研究这个正整数序列,他希望找到序列中的两个数 ai, aj (1 ≤ i < j ≤ n),满足 在 之间,即 。请你帮他解决这个问题。
本题数据规模较大,因此采用了较为特别的输入方式。具体来说,我们输入序列的前 m (1 ≤ m ≤ min(n, 3 × 105)) 项,后面的 n - m 项则采用一定的规则生成。若 m < n,那么生成规则为: (m ≤ i < n),其中 b, c, t 在输入中给出, 为 z 除以 t 的最小非负余数。
Input第一行包含三个整数 n, p, q (2 ≤ n ≤ 3 × 107, 1 ≤ p < q ≤ 104),含义见题目描述。
第二行包含四个整数 m, b, c, t (1 ≤ m ≤ min(n, 3 × 105), 0 ≤ b, c < t ≤ 109),含义见题目描述。
第三行包含 m 个整数,第 i 个为 ai (1 ≤ ai ≤ t)。
Output如果无解,输出一行一个整数 - 1。
如果存在解,则输出一行两个整数 i, j,表示 ai, aj 满足题目要求,两个整数以一个空格分隔。i, j 应当满足 1 ≤ i < j ≤ n。
如果有多种答案,输出任意一个即可。
ExamplesInput3 1 2 3 0 0 100 1 2 5Output
1 2Input
2 1 2 2 0 0 100 1 3Output
-1Input
3 2 5 1 2 1 998244353 1Output
2 3Note
对于第一个样例,正整数序列为 1, 2, 5,其中 。
对于第二个样例,正整数序列为 1, 3。由于 ,因此不存在满足要求的答案。
对于第三个样例,正整数序列为 1, 4, 10,其中 。