/ 
実行時間制限: 3 sec / メモリ制限: 1024 MiB
配点 : 600 点
問題文
整数列 A = (A_1, A_2, \dots, A_N) および整数 X が与えられます。
次の条件を全て満たす整数の組 (i, j, k) を 1 組出力してください。条件を満たす組が存在しない場合はそのことを報告してください。
- 1 \leq i \lt j \lt k \leq N
- A_i + A_j + A_k = X
制約
- 3 \leq N \leq 10^6
- 1 \leq X \leq 10^6
- 1 \leq A_i \leq X
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N X A_1 A_2 \dots A_N
出力
条件を満たす整数の組 (i, j, k) が存在する場合、以下の形式で出力せよ。答えが複数ある場合はどれを出力しても良い。
i j k
条件を満たす整数の組が存在しない場合、-1 を出力せよ。
入力例 1
5 16 1 8 5 10 13
出力例 1
1 3 4
(i, j, k) = (1, 3, 4) は 1 \leq i \lt j \lt k \leq N かつ A_i + A_j + A_k = 1 + 5 + 10 = 16 = X を満たします。
入力例 2
5 20 1 8 5 10 13
出力例 2
-1
入力例 3
10 100000 73766 47718 74148 49218 76721 31902 21994 18880 29598 98917
出力例 3
4 6 8
Score : 600 points
Problem Statement
You are given an integer sequence A = (A_1, A_2, \dots, A_N) and an integer X.
Print one triple of integers (i, j, k) satisfying all of the following conditions. If no such triple exists, report that fact.
- 1 \leq i \lt j \lt k \leq N
- A_i + A_j + A_k = X
Constraints
- 3 \leq N \leq 10^6
- 1 \leq X \leq 10^6
- 1 \leq A_i \leq X
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N X A_1 A_2 \dots A_N
Output
If there exists an integer triple (i, j, k) satisfying the conditions, print one in the following format. If there are multiple solutions, you may print any of them.
i j k
If no such triple exists, print -1.
Sample Input 1
5 16 1 8 5 10 13
Sample Output 1
1 3 4
The triple (i, j, k) = (1, 3, 4) satisfies 1 \leq i \lt j \lt k \leq N and A_i + A_j + A_k = 1 + 5 + 10 = 16 = X.
Sample Input 2
5 20 1 8 5 10 13
Sample Output 2
-1
Sample Input 3
10 100000 73766 47718 74148 49218 76721 31902 21994 18880 29598 98917
Sample Output 3
4 6 8