TopCoder

abcabcabc

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

Description

現在桌上擺了一共 $N$ 個堅果，每個堅果有 $M$ 個屬性。

現在你發現到當把兩個不同的堅果一起吃後，可以得到兩個堅果屬性合併的美味度，具體來說如果現在有兩個堅果的屬性分別為 $A = [a_1, a_2, \ldots, a_M]$、$B = [b_1, b_2, \ldots, b_M]$，則把兩個堅果一起吃之後便可以得到 $\sum\limits_{i = 1}^ M a_i \times b_i$ 的美味度。

在嘗試一堆組合的方式之後，你發現兩個堅果合併的美味度有可能是奇數！

這樣實在是太衰了，請找出一種方法可以找到兩個不同的堅果合併後美味度是偶數。

Input Format

輸入的第一行有一個正整數 $T$ 代表測試資料的筆數。

對於每筆測試資料的第一行有兩個正整數 $N$、$M$，分別代表桌上的堅果數量以及屬性數量。

接下來一共有 $N$ 行，每行有 $M$ 個數字 $m_1, m_2, \ldots, m_M$，中間沒有空格隔開，代表每個堅果的各個屬性。

$1 \le T \le 2$
$2 \le N, M \le 10 ^ 7$
$N \times M \le 10 ^ 7$
$0 \le m_1, m_2, \ldots, m_M \le 1$

Output Format

對於每筆測試資料，請輸出兩個整數 $a, b$ 滿足 $1 \le a < b \le N$ 且第 $a$ 個堅果和第 $b$ 個堅果合併後的美味度是偶數。如果找不到滿足條件的堅果對，請輸出 -1。

若有多組合法的解，你可以輸出任意一組。

Sample Input 1

2
2 2
10
01
2 2
11
01

Sample Output 1

1 2
-1

Hints

Problem Source

IOICamp 2020 Day5 pE

No.	Testdata Range	Constraints	Score
1	0	範例測資	0
2	0~34	無額外限制	100

Testdata and Limits

No.	Time Limit (ms)	Memory Limit (VSS, KiB)	Output Limit (KiB)	Subtasks
0	4000	1048576	65536	1 2
1	4000	1048576	65536	2
2	4000	1048576	65536	2
3	4000	1048576	65536	2
4	4000	1048576	65536	2
5	4000	1048576	65536	2
6	4000	1048576	65536	2
7	4000	1048576	65536	2
8	4000	1048576	65536	2
9	4000	1048576	65536	2
10	4000	1048576	65536	2
11	4000	1048576	65536	2
12	4000	1048576	65536	2
13	4000	1048576	65536	2
14	4000	1048576	65536	2
15	4000	1048576	65536	2
16	4000	1048576	65536	2
17	4000	1048576	65536	2
18	4000	1048576	65536	2
19	4000	1048576	65536	2
20	4000	1048576	65536	2
21	4000	1048576	65536	2
22	4000	1048576	65536	2
23	4000	1048576	65536	2
24	4000	1048576	65536	2
25	4000	1048576	65536	2
26	4000	1048576	65536	2
27	4000	1048576	65536	2
28	4000	1048576	65536	2
29	4000	1048576	65536	2
30	4000	1048576	65536	2
31	4000	1048576	65536	2
32	4000	1048576	65536	2
33	4000	1048576	65536	2
34	4000	1048576	65536	2

268 . 最好吃的堅果