提示: 欢迎访问OurACM平台。
Problem 1400 平方数

Accept: 126    Submit: 584
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

给出包含M个数字的列表,和列表中所有数字的所有质因数。求出最长的子列表,使得子列表中所有数字的乘积是一个完全平方数。

Input

输入文件包含多组测试数据。第一行包含两个整数N , M ( 1 <= N <= 30 , 1 <= M <= 30000 ). N 是质因数的个数。接下来一行有N个整数,给出所有的质因数。然后一行包含M个整数,给出列表。

输入文件结束于N = M = 0.

Output

对于每组数据,输出最长子列表的两个位置坐标l r。l是该子列表在列表中的起始位置,r是结束位置。如果多种情况都满足子列表长度最大,输出l最小的一个。如果不存在这样的子列表输出“None”。

Sample Input

3 4 2 3 5 4 9 25 6 3 4 2 3 5 6 6 3 3 0 0

Sample Output

1 3 1 4

Source

Andy Zhau's Contest No.1

Submit  Back  Status  Discuss