8610: Yet Another FFT Problem?

内存限制:1024 MB 时间限制:4 S
题面:传统 评测方式:文本比较 上传者:
提交:3 通过:0

题目描述

triplea and tripleb have two integer arrays A=[a1,a2,…,an] and B=[b1,b2,…,bm], respectively. One day they came up with the following problem:
  • Does there exists a pair of numbers in arrays A and B, such that their absolute difference is the same?

However, triplea and tripleb care about their data privacy, so they don't want to expose their array directly to each other. That's why they turn to you------triplec. Can you help them solve this problem?

Formally, you need to determine: do there exist four indices 1≤i,j≤n,1≤k,l≤m, such that i≠j, k≠l and |ai-aj|=|bk-bl|.

输入格式

The first line contains two integers n,m(2≤n,m≤106), denoting the sizes of array A and B, respectively.
The next line contains n integers a1,a2,…,an(0≤ai≤107), denoting the elements of array A.
The next line contains m integers b1,b2,…,bm(0≤bi≤107), denoting the elements of array B.

输出格式

If there exist four indices 1≤i,j≤n,1≤k,l≤m, such that i≠j, k≠l and |ai-aj|=|bk-bl|, output i,j,k,l in a line, otherwise output 1 in a line.

输入样例 复制

4 4
2 4 8 16
3 9 27 81

输出样例 复制

1 3 1 2