結果

問題 No.3506 All Distance is Square Number
コンテスト
ユーザー GOTKAKO
提出日時 2026-04-18 03:46:52
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 23,737 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,296 ms
コンパイル使用メモリ 212,736 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2026-04-18 03:46:58
合計ジャッジ時間 5,086 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2 WA * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

random_device rnd;
mt19937 mt(rnd());

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<string> answer = {
        "-1",
        "-1",
        "1\n1 2 1\n1 1\n",
        "3\n1 2 1\n1 3 4\n2 3 9\n1 1\n1 2\n1 3\n",
        "5\n1 2 1\n2 3 3\n3 4 5\n1 4 12\n2 3 4\n1 1\n2 1 2\n3 1 2 3\n5 1 4 3 2 5\n2 5 3\n3 2 1 4\n",
        "7\n1 2 1\n2 3 3\n3 4 5\n4 5 7\n1 5 12\n2 3 4\n3 4 8\n1 1\n2 1 2\n3 1 2 3\n4 1 2 3 4\n4 1 5 4 3\n2 6 3\n3 6 3 4\n6 2 1 5 4 3 7\n3 2 1 5\n4 7 6 1 5\n",
        "9\n1 2 1\n2 3 3\n3 4 5\n4 5 7\n5 6 9\n1 6 8\n2 3 2\n3 4 16\n4 5 6\n1 1\n2 1 2\n3 1 2 3\n4 1 2 3 4\n5 1 2 3 4 5\n5 7 3 4 9 8\n4 1 6 5 4\n7 2 7 1 6 5 4 9\n2 1 6\n7 2 1 6 5 4 3 8\n4 2 7 3 9\n5 2 7 3 9 5\n5 3 7 1 6 5\n4 3 7 1 6\n1 5\n",
        "11\n1 2 1\n2 3 3\n3 4 5\n4 5 7\n5 6 9\n6 7 11\n1 7 16\n2 3 20\n3 4 6\n4 5 12\n5 6 2\n1 1\n2 1 2\n3 1 2 3\n4 1 2 3 4\n5 1 2 3 4 5\n6 1 2 3 4 5 6\n6 1 7 6 5 4 3\n5 1 7 6 5 10\n6 1 7 6 11 4 10\n9 2 3 4 10 9 8 1 7 6\n10 2 3 4 5 11 10 9 8 1 7\n6 8 1 7 6 5 4\n4 2 8 9 4\n5 2 8 3 10 5\n6 2 8 9 4 11 6\n8 3 2 1 7 6 5 4 10\n5 3 2 1 7 6\n4 3 2 1 7\n1 5\n5 4 3 8 1 7\n6 5 10 9 8 1 7\n",
        "13\n1 2 1\n2 3 3\n3 4 5\n4 5 7\n5 6 9\n6 7 11\n7 8 13\n1 8 18\n2 3 12\n3 4 10\n4 5 22\n5 6 16\n6 7 20\n1 1\n2 1 2\n3 1 2 3\n4 1 2 3 4\n5 1 2 3 4 5\n6 1 2 3 4 5 6\n7 1 2 3 4 5 6 7\n7 1 8 7 6 5 4 3\n8 1 8 7 6 12 4 3 10\n7 1 8 7 6 5 4 11\n10 1 8 7 13 5 4 3 10 11 12\n5 2 10 4 5 13\n6 2 3 4 12 13 7\n5 2 9 3 4 11\n6 2 1 8 7 13 5\n9 2 1 8 7 6 5 4 11 12\n12 3 4 5 6 7 8 1 9 10 11 12 13\n7 2 9 10 4 12 13 7\n7 10 2 1 8 7 13 12\n2 4 5\n7 3 2 9 10 4 12 6\n4 3 9 1 8\n7 4 10 9 1 8 7 13\n6 4 3 10 11 5 6\n7 5 12 4 10 2 1 8\n3 5 12 6\n4 5 12 6 7\n7 6 12 11 10 2 1 8\n",
        "15\n1 2 1\n2 3 3\n3 4 5\n4 5 7\n5 6 9\n6 7 11\n7 8 13\n8 9 15\n1 9 22\n2 3 26\n3 4 24\n4 5 6\n5 6 14\n6 7 8\n7 8 2\n1 1\n2 1 2\n3 1 2 3\n4 1 2 3 4\n5 1 2 3 4 5\n6 1 2 3 4 5 6\n7 1 2 3 4 5 6 7\n8 1 2 3 4 5 6 7 8\n10 1 9 8 15 6 5 12 3 2 10\n9 1 9 8 15 6 13 12 3 11\n8 1 9 8 7 14 5 4 12\n9 2 10 1 9 8 15 14 5 13\n7 2 3 12 5 6 7 15\n6 2 3 12 5 6 15\n7 2 3 4 5 14 15 8\n8 2 1 9 8 7 6 5 4\n11 2 1 9 8 7 6 13 4 3 11 12\n5 2 10 3 12 5\n8 2 10 3 4 13 6 7 15\n7 2 10 3 12 13 14 15\n6 3 4 5 6 15 8\n8 3 2 1 9 8 7 14 13\n6 3 11 4 5 6 14\n9 3 2 10 11 4 5 6 7 15\n8 3 2 10 11 4 13 14 7\n7 3 11 4 5 14 7 8\n10 4 3 2 1 9 8 7 6 5 13\n6 4 3 11 12 13 14\n7 4 3 11 12 5 6 15\n10 4 3 2 10 11 12 13 14 7 8\n8 5 4 3 2 1 9 8 15\n9 5 4 3 10 1 9 8 7 15\n7 5 4 12 13 6 15 8\n8 6 13 12 3 10 1 9 8\n7 6 5 4 3 10 1 9\n5 7 6 14 15 8\n",
        "17\n1 2 1\n2 3 3\n3 4 5\n4 5 7\n5 6 9\n6 7 11\n7 8 13\n8 9 15\n9 10 17\n1 10 8\n2 3 6\n3 4 28\n4 5 22\n5 6 18\n6 7 10\n7 8 14\n8 9 30\n1 1\n2 1 2\n3 1 2 3\n4 1 2 3 4\n5 1 2 3 4 5\n6 1 2 3 4 5 6\n7 1 2 3 4 5 6 7\n8 1 2 3 4 5 6 7 8\n9 1 2 3 4 5 6 7 8 9\n9 1 10 9 8 7 15 5 13 3\n8 1 10 9 8 7 6 5 4\n13 1 10 9 8 7 15 5 4 3 2 11 12 13\n10 1 10 9 8 7 6 5 4 13 14\n13 2 3 12 11 1 10 9 8 7 6 5 14 15\n6 2 3 4 5 6 16\n7 2 3 4 5 6 16 8\n2 1 10\n9 2 1 10 9 8 16 6 5 13\n10 2 1 10 9 17 7 6 5 4 13\n11 3 4 13 12 2 1 10 9 17 7 15\n10 2 1 10 9 17 16 6 5 14 15\n15 2 1 10 9 17 7 6 5 4 3 12 13 14 15 16\n8 2 11 3 13 5 6 16 17\n9 2 11 3 4 5 15 7 17 9\n9 3 2 1 10 9 8 7 15 5\n10 3 2 1 10 9 8 7 6 5 14\n7 3 11 1 10 9 17 16\n6 3 2 1 10 9 8\n9 3 2 11 12 4 14 6 7 17\n10 3 2 11 12 13 5 6 7 17 9\n9 4 3 2 1 10 9 8 16 6\n8 4 3 2 11 12 13 14 6\n13 4 12 2 1 10 9 17 7 6 5 14 15 16\n10 4 3 2 11 12 13 14 6 16 17\n11 4 3 2 11 12 13 14 15 7 8 9\n11 5 4 3 2 1 10 9 8 16 6 15\n10 5 4 3 2 11 12 13 14 15 7\n9 5 4 3 12 13 14 6 16 17\n12 5 4 3 2 11 12 13 14 6 7 17 9\n11 6 5 4 3 11 1 10 9 17 7 16\n8 6 5 4 3 11 1 10 9\n5 6 15 7 17 9\n9 7 6 5 4 12 11 1 10 9\n12 7 6 5 4 3 12 13 14 15 16 8 9\n9 8 7 6 14 4 3 2 1 10\n",
        "19\n1 2 1\n2 3 3\n3 4 5\n4 5 7\n5 6 9\n6 7 11\n7 8 13\n8 9 15\n9 10 17\n10 11 19\n1 11 24\n2 3 8\n3 4 4\n4 5 14\n5 6 12\n6 7 30\n7 8 10\n8 9 32\n9 10 26\n1 1\n2 1 2\n3 1 2 3\n4 1 2 3 4\n5 1 2 3 4 5\n6 1 2 3 4 5 6\n7 1 2 3 4 5 6 7\n8 1 2 3 4 5 6 7 8\n9 1 2 3 4 5 6 7 8 9\n10 1 2 3 4 5 6 7 8 9 10\n10 1 11 10 9 8 7 6 5 4 3\n11 1 11 10 9 8 7 16 5 4 3 13\n14 1 11 10 9 8 7 16 5 4 3 2 12 13 14\n7 1 11 10 9 8 7 6\n12 1 11 10 9 8 17 6 5 4 14 15 16\n15 2 3 4 5 6 16 15 14 13 12 1 11 10 9 18\n16 2 3 4 5 6 7 17 16 15 14 13 12 1 11 10 19\n15 2 3 4 5 15 14 13 12 1 11 10 9 8 18 19\n2 1 11\n12 2 1 11 10 9 8 17 16 5 4 3 13\n11 2 1 11 10 9 18 7 16 5 4 14\n8 2 1 11 10 9 8 17 6\n6 2 12 13 4 15 16\n10 2 1 11 10 19 18 7 6 16 17\n5 2 1 11 10 9\n9 2 12 3 4 5 16 17 18 9\n10 2 12 3 4 5 6 17 18 9 10\n12 3 2 1 11 10 19 8 7 16 15 4 14\n13 3 2 1 11 10 9 8 7 16 5 4 14 15\n10 3 2 1 11 10 19 8 17 6 16\n13 3 2 1 11 10 9 8 7 6 5 15 16 17\n11 3 2 12 13 4 15 6 7 8 9 19\n10 3 2 12 13 4 15 6 7 18 19\n11 3 2 12 13 4 5 16 17 18 9 10\n12 4 3 2 1 11 10 9 18 17 16 5 15\n9 4 3 2 1 11 10 9 18 7\n8 4 3 2 1 11 10 19 8\n13 4 3 2 1 11 10 19 8 7 6 16 17 18\n6 4 3 12 1 11 10\n12 4 3 2 12 13 14 5 16 7 8 9 10\n10 5 4 3 12 1 11 10 19 18 7\n9 5 4 3 2 1 11 10 9 8\n14 5 4 3 2 1 11 10 9 8 7 6 16 17 18\n12 5 4 3 2 12 13 14 15 6 7 18 19\n6 5 4 3 2 1 11\n10 6 5 14 3 2 1 11 10 19 18\n9 6 5 4 13 12 1 11 10 9\n12 6 5 4 3 2 1 11 10 9 8 18 19\n7 6 5 4 13 12 1 11\n12 7 6 5 4 13 12 1 11 10 19 8 18\n9 7 6 15 4 3 12 1 11 10\n8 7 6 15 4 3 12 1 11\n10 8 7 6 15 14 13 12 1 11 10\n9 8 7 6 5 14 3 12 1 11\n10 9 8 17 16 5 4 3 2 1 11\n",
        "21\n1 2 1\n2 3 3\n3 4 5\n4 5 7\n5 6 9\n6 7 11\n7 8 13\n8 9 15\n9 10 17\n10 11 19\n11 12 21\n1 12 16\n2 3 32\n3 4 34\n4 5 6\n5 6 26\n6 7 10\n7 8 2\n8 9 8\n9 10 22\n10 11 4\n1 1\n2 1 2\n3 1 2 3\n4 1 2 3 4\n5 1 2 3 4 5\n6 1 2 3 4 5 6\n7 1 2 3 4 5 6 7\n8 1 2 3 4 5 6 7 8\n9 1 2 3 4 5 6 7 8 9\n10 1 2 3 4 5 6 7 8 9 10\n11 1 2 3 4 5 6 7 8 9 10 11\n13 1 12 11 10 9 8 7 6 5 4 3 2 13\n10 1 12 11 10 9 8 7 17 16 15\n9 1 12 11 10 9 8 7 17 5\n8 1 12 11 10 20 19 18 6\n7 1 12 11 10 20 19 7\n18 1 12 11 21 9 19 7 6 5 4 3 2 13 14 15 16 17 18\n17 1 12 11 10 20 8 7 6 5 4 3 14 15 16 17 18 19\n6 1 12 11 21 9 20\n7 1 12 11 10 9 20 21\n10 2 3 4 16 17 7 8 9 21 11\n13 2 1 12 11 10 9 8 7 17 5 15 3 14\n12 2 1 12 11 10 9 8 18 6 16 4 15\n15 2 1 12 11 10 9 19 7 6 5 4 3 14 15 16\n10 2 1 12 11 21 9 8 18 6 17\n15 2 1 12 11 10 9 19 7 6 5 4 15 16 17 18\n8 2 1 12 11 10 9 8 19\n9 2 13 3 4 5 17 18 8 9\n6 2 1 12 11 10 21\n11 2 13 3 4 5 17 7 19 9 10 11\n11 3 2 1 12 11 10 20 19 7 17 16\n10 3 2 1 12 11 10 9 8 7 6\n13 3 2 1 12 11 21 9 19 7 6 5 16 17\n12 3 14 4 16 17 18 8 9 10 21 20 19\n9 3 2 13 14 4 5 17 7 19\n18 3 2 1 12 11 21 9 8 7 6 5 4 15 16 17 18 19 20\n11 3 2 13 14 4 5 6 18 8 20 21\n4 3 2 1 12\n11 4 3 2 1 12 11 10 9 19 7 6\n10 4 3 2 1 12 11 21 20 19 7\n13 4 3 13 1 12 11 10 9 8 7 6 17 18\n14 4 3 2 13 14 15 5 17 7 8 9 10 21 20\n13 4 3 2 13 14 15 5 6 18 8 20 10 21\n12 4 3 2 13 14 15 5 6 7 19 20 10\n13 4 3 2 13 14 15 5 17 7 8 20 10 11\n11 5 4 3 2 1 12 11 21 9 8 18\n12 5 4 3 2 1 12 11 10 9 19 7 18\n11 5 4 3 2 1 12 11 10 9 8 19\n8 5 4 3 2 1 12 11 10\n13 5 4 3 2 13 14 15 16 6 18 19 20 21\n14 5 4 3 2 13 14 15 16 6 7 19 9 21 11\n13 6 5 4 3 2 1 12 11 10 20 8 7 18\n12 6 5 15 3 2 1 12 11 21 20 8 19\n15 6 5 4 3 2 1 12 11 10 9 8 7 18 19 20\n14 6 5 4 3 2 13 14 15 16 17 18 8 9 10\n7 6 5 4 3 13 1 12\n11 7 6 5 15 3 2 1 12 11 10 9\n12 7 6 5 4 3 2 1 12 11 10 9 20\n9 7 6 5 4 14 13 1 12 11\n8 7 6 5 15 3 2 1 12\n13 8 7 6 5 4 3 2 1 12 11 21 9 20\n10 8 7 6 5 15 3 2 1 12 11\n13 8 7 6 5 4 15 16 17 18 19 20 10 11\n13 9 8 7 6 5 15 3 13 1 12 11 10 21\n16 9 8 7 6 5 4 3 14 15 16 17 18 19 20 10 11\n11 10 9 8 7 6 5 15 3 13 1 12\n",
        "23\n1 2 1\n2 3 3\n3 4 5\n4 5 7\n5 6 9\n6 7 11\n7 8 13\n8 9 15\n9 10 17\n10 11 19\n11 12 21\n12 13 23\n1 13 10\n2 3 16\n3 4 12\n4 5 8\n5 6 4\n6 7 38\n7 8 30\n8 9 34\n9 10 22\n10 11 14\n11 12 36\n1 1\n2 1 2\n3 1 2 3\n4 1 2 3 4\n5 1 2 3 4 5\n6 1 2 3 4 5 6\n7 1 2 3 4 5 6 7\n8 1 2 3 4 5 6 7 8\n9 1 2 3 4 5 6 7 8 9\n10 1 2 3 4 5 6 7 8 9 10\n11 1 2 3 4 5 6 7 8 9 10 11\n12 1 2 3 4 5 6 7 8 9 10 11 12\n12 1 13 12 11 10 9 8 19 6 5 16 3\n11 1 13 12 11 10 9 8 7 18 17 16\n10 1 13 12 11 10 21 8 7 6 5\n9 1 13 12 11 22 9 8 19 18\n14 1 13 12 11 10 9 8 7 6 5 4 16 17 18\n9 1 13 12 11 22 9 8 7 19\n9 2 3 4 5 6 7 20 9 21\n19 2 3 4 5 6 7 8 20 19 18 17 16 15 14 1 13 12 23 22\n20 2 3 4 5 6 18 17 16 15 14 1 13 12 11 10 9 8 20 21 22\n10 2 3 4 5 6 7 20 21 10 11\n11 2 3 4 17 6 19 20 9 22 11 12\n12 2 1 13 12 11 10 9 8 7 6 17 4\n15 2 1 13 12 11 10 9 8 7 6 17 4 3 15 16\n10 2 1 13 12 11 10 9 20 19 6\n9 2 1 13 12 11 10 21 8 19\n12 2 1 13 12 11 10 21 20 7 6 18 19\n11 2 1 13 12 23 22 9 8 7 19 20\n13 2 14 3 4 17 18 19 8 9 10 11 23 22\n12 2 14 3 4 5 6 7 20 21 10 11 23\n11 2 14 3 16 5 6 19 8 9 10 23\n12 2 14 3 4 5 6 7 8 9 22 23 12\n12 3 2 1 13 12 11 10 9 8 7 18 17\n11 3 2 1 13 12 11 22 9 20 19 6\n10 3 2 1 13 12 11 10 9 8 19\n13 3 2 1 13 12 11 10 9 20 7 6 18 19\n12 3 2 1 13 12 11 10 21 8 7 19 20\n9 3 2 1 13 12 11 10 9 21\n18 3 2 1 13 12 11 10 9 8 7 6 5 17 18 19 20 21 22\n12 3 2 14 15 16 5 6 7 8 9 22 11\n13 3 2 14 15 4 5 18 19 8 9 22 23 12\n12 4 3 2 1 13 12 11 10 21 20 7 6\n15 4 3 2 1 13 12 11 10 9 8 7 6 5 17 18\n10 4 3 2 1 13 12 11 10 9 8\n9 4 3 2 1 13 12 23 10 9\n11 4 3 2 14 15 16 5 6 7 8 21\n12 4 3 2 14 15 16 17 6 7 20 9 22\n6 4 3 2 1 13 12\n14 4 3 2 14 15 16 5 6 19 8 9 10 11 12\n14 5 4 3 14 1 13 12 23 10 9 20 19 6 18\n11 5 4 3 2 1 13 12 11 22 9 20\n16 5 4 3 2 1 13 12 11 10 9 8 7 6 18 19 20\n13 5 4 3 2 1 13 12 23 22 9 8 20 21\n15 5 4 3 2 14 15 16 17 6 7 8 9 10 11 23\n14 5 4 3 2 14 15 16 17 6 19 20 9 10 11\n15 5 4 3 2 14 15 16 17 18 7 8 9 10 23 12\n12 6 5 4 3 14 1 13 12 23 10 9 8\n11 6 5 4 3 2 1 13 12 11 22 9\n15 6 5 4 3 2 14 15 16 17 18 7 8 21 10 22\n14 6 5 4 3 2 14 15 16 17 18 7 20 9 10\n15 6 5 4 3 2 14 15 16 17 18 19 8 9 22 23\n7 6 17 16 15 2 1 13\n12 7 6 5 4 3 2 1 13 12 11 10 21\n15 7 6 5 4 3 2 1 13 12 23 10 9 8 20 21\n16 7 6 5 16 3 2 1 13 12 11 10 9 8 20 21 22\n15 7 6 5 16 3 14 1 13 12 11 10 9 21 22 23\n17 7 6 5 4 3 2 14 15 16 17 18 19 8 21 10 11 12\n12 8 7 6 5 4 15 2 1 13 12 11 10\n15 8 7 6 5 4 15 14 1 13 12 23 10 9 21 22\n12 8 7 6 17 4 15 14 1 13 12 11 23\n9 8 7 6 5 4 15 2 1 13\n14 9 8 7 6 5 4 3 14 1 13 12 23 10 22\n11 9 8 7 6 5 4 15 2 1 13 12\n13 9 8 7 6 5 17 18 19 20 21 10 11 12\n14 10 9 8 7 18 5 16 15 2 1 13 12 11 23\n11 10 9 8 7 18 5 4 15 2 1 13\n12 11 10 9 8 7 6 5 4 3 14 1 13\n",
        "25\n1 2 1\n2 3 3\n3 4 5\n4 5 7\n5 6 9\n6 7 11\n7 8 13\n8 9 15\n9 10 17\n10 11 19\n11 12 21\n12 13 23\n13 14 25\n1 14 38\n2 3 24\n3 4 40\n4 5 8\n5 6 2\n6 7 28\n7 8 4\n8 9 10\n9 10 32\n10 11 18\n11 12 34\n12 13 12\n1 1\n2 1 2\n3 1 2 3\n4 1 2 3 4\n5 1 2 3 4 5\n6 1 2 3 4 5 6\n7 1 2 3 4 5 6 7\n8 1 2 3 4 5 6 7 8\n9 1 2 3 4 5 6 7 8 9\n10 1 2 3 4 5 6 7 8 9 10\n11 1 2 3 4 5 6 7 8 9 10 11\n12 1 2 3 4 5 6 7 8 9 10 11 12\n13 1 2 3 4 5 6 7 8 9 10 11 12 13\n15 1 14 13 12 11 10 9 8 7 6 18 17 3 2 15\n16 1 14 13 12 11 10 9 8 7 19 5 17 3 2 15 16\n17 1 14 13 12 11 10 9 8 7 19 18 4 3 2 15 16 17\n18 1 14 13 12 11 10 9 8 20 19 5 4 3 2 15 16 17 18\n19 1 14 13 12 11 10 22 8 7 6 5 4 3 2 15 16 17 18 19\n16 1 14 13 12 11 10 22 8 7 6 5 4 17 18 19 20\n7 1 14 13 12 11 10 9\n14 1 14 13 12 11 23 9 8 7 6 19 20 21 22\n5 1 14 13 12 24\n20 1 14 13 25 11 10 9 8 7 6 5 4 17 18 19 20 21 22 23 24\n3 1 14 13\n12 2 3 4 5 6 7 8 9 23 24 25 13\n13 2 1 14 13 12 11 10 9 8 7 6 18 17\n12 2 1 14 13 12 11 10 9 8 20 19 18\n17 2 1 14 13 12 11 10 22 8 7 19 5 4 3 16 17 18\n14 2 1 14 13 12 11 10 9 8 7 6 5 18 19\n19 2 1 14 13 12 11 10 9 8 7 6 5 4 3 16 17 18 19 20\n14 2 1 14 13 12 24 10 22 8 7 6 19 20 21\n13 2 15 3 4 5 6 7 8 9 10 11 24 23\n18 2 1 14 13 12 11 10 9 8 7 6 5 18 19 20 21 22 23\n13 2 1 14 13 12 11 10 9 8 21 22 23 24\n18 2 1 14 13 12 11 10 9 8 7 6 19 20 21 22 23 24 25\n13 2 15 3 4 5 6 7 8 22 10 11 25 13\n15 3 2 1 14 13 12 11 10 9 8 7 19 18 4 17\n16 3 2 1 14 13 12 11 10 9 8 20 19 5 4 17 18\n15 3 2 1 14 13 12 11 10 9 21 7 6 5 18 19\n12 3 2 1 14 13 12 24 23 9 8 7 20\n17 3 2 1 14 13 12 24 23 9 8 7 6 5 18 19 20 21\n14 3 2 1 14 13 12 11 23 9 8 7 20 21 22\n11 3 2 15 16 4 5 6 20 8 22 10\n12 3 2 1 14 13 25 11 10 9 22 23 24\n13 3 2 15 16 4 5 6 7 8 9 10 11 25\n14 3 2 15 16 4 5 6 20 8 9 10 24 25 13\n13 4 3 2 1 14 13 12 11 10 22 21 7 19\n14 4 3 2 1 14 13 12 11 23 9 8 7 6 19\n11 4 3 2 1 14 13 12 11 10 9 21\n12 4 3 2 1 14 13 12 24 23 9 8 21\n9 4 3 2 1 14 13 25 24 10\n14 4 3 2 15 16 17 5 6 7 8 9 23 11 24\n19 4 3 2 1 14 13 12 11 10 9 8 7 6 19 20 21 22 23 24\n10 4 3 2 1 14 13 12 11 24 25\n15 4 3 2 15 16 17 5 6 7 8 22 23 24 25 13\n13 5 4 3 2 1 14 13 12 11 10 9 8 7\n12 5 4 3 2 1 14 13 12 24 10 9 8\n15 5 4 3 2 1 14 13 12 11 10 22 8 7 20 21\n14 5 4 3 2 1 14 13 12 11 10 9 8 21 22\n11 5 4 3 2 1 14 13 12 11 10 23\n8 5 4 3 2 1 14 13 25\n17 5 4 3 2 1 14 13 12 11 10 9 8 21 22 23 24 25\n16 5 4 3 2 15 16 17 18 6 7 8 22 23 11 12 13\n15 6 5 4 3 2 1 14 13 12 11 23 22 8 7 20\n16 6 5 4 3 2 1 14 13 25 11 10 22 8 7 20 21\n15 6 5 4 3 2 1 14 13 25 11 10 9 8 21 22\n12 6 5 4 3 2 1 14 13 25 11 10 23\n17 6 5 4 3 2 15 16 17 18 19 7 8 9 23 11 12 25\n16 6 5 4 3 2 15 16 17 18 19 7 21 22 23 24 25\n17 6 5 4 3 2 15 16 17 18 19 20 8 22 10 24 12 13\n13 7 6 5 4 3 2 1 14 13 25 11 10 22\n14 7 6 5 4 3 2 1 14 13 25 24 23 9 22\n11 7 6 5 4 3 2 1 14 13 12 24\n16 7 6 5 4 3 2 15 16 17 18 19 20 8 9 23 11\n17 7 6 5 4 3 2 15 16 17 18 19 20 21 9 23 24 12\n18 7 6 5 4 3 2 15 16 17 18 19 20 8 22 10 11 12 13\n15 8 7 6 5 4 3 2 15 16 17 18 19 20 21 9\n14 8 7 6 5 4 16 2 1 14 13 12 24 10 23\n17 8 7 6 5 4 3 16 17 18 19 20 21 9 23 24 12 25\n18 8 7 6 5 4 3 15 1 14 13 12 11 10 9 22 23 24 25\n17 8 7 6 5 4 3 16 17 18 19 20 21 9 23 11 12 13\n15 9 8 7 6 5 4 3 2 1 14 13 12 11 10 23\n18 9 8 7 6 5 4 3 16 17 18 19 20 21 22 10 24 12 25\n11 9 8 7 6 5 4 3 2 1 14 13\n18 9 8 7 6 5 4 3 16 17 18 19 20 21 22 10 11 12 13\n13 10 9 8 7 6 5 4 3 15 1 14 13 25\n16 10 9 8 7 6 5 17 16 2 1 14 13 12 11 24 25\n13 10 9 8 7 6 19 20 21 22 23 11 25 13\n15 11 10 9 8 7 6 5 18 19 20 21 22 23 24 12\n12 11 10 9 8 7 19 18 4 3 2 1 14\n13 12 11 10 9 8 7 6 18 4 3 15 1 14\n",
        "27\n1 2 1\n2 3 3\n3 4 5\n4 5 7\n5 6 9\n6 7 11\n7 8 13\n8 9 15\n9 10 17\n10 11 19\n11 12 21\n12 13 23\n13 14 25\n14 15 27\n1 15 30\n2 3 16\n3 4 14\n4 5 10\n5 6 44\n6 7 4\n7 8 6\n8 9 36\n9 10 40\n10 11 34\n11 12 20\n12 13 28\n13 14 42\n1 1\n2 1 2\n3 1 2 3\n4 1 2 3 4\n5 1 2 3 4 5\n6 1 2 3 4 5 6\n7 1 2 3 4 5 6 7\n8 1 2 3 4 5 6 7 8\n9 1 2 3 4 5 6 7 8 9\n10 1 2 3 4 5 6 7 8 9 10\n11 1 2 3 4 5 6 7 8 9 10 11\n12 1 2 3 4 5 6 7 8 9 10 11 12\n13 1 2 3 4 5 6 7 8 9 10 11 12 13\n14 1 2 3 4 5 6 7 8 9 10 11 12 13 14\n16 1 15 14 13 12 11 10 9 8 7 6 19 18 17 2 16\n17 1 15 14 13 12 11 10 9 8 7 6 5 4 3 2 16 17\n14 1 15 14 13 12 11 10 9 8 7 20 19 4 18\n19 1 15 14 13 12 11 10 9 22 7 20 5 4 3 2 16 17 18 19\n18 1 15 14 13 12 11 24 9 22 21 6 5 4 3 17 18 19 20\n19 1 15 14 13 12 11 10 23 8 7 6 5 4 3 17 18 19 20 21\n16 1 15 14 13 12 11 10 23 8 7 6 5 19 20 21 22\n17 1 15 14 13 26 11 24 9 8 7 6 5 19 20 21 22 23\n6 1 15 14 27 12 11\n19 1 15 14 13 26 11 10 9 8 7 6 5 19 20 21 22 23 24 25\n4 1 15 14 27\n21 2 3 4 5 6 7 8 9 10 24 23 22 21 20 19 18 17 16 1 15 14\n13 2 3 4 5 6 7 22 23 10 11 12 27 14\n14 2 1 15 14 13 12 11 10 9 8 7 6 19 4\n13 2 1 15 14 13 12 11 10 9 22 21 20 19\n16 2 1 15 14 13 12 11 10 9 22 7 20 5 4 18 19\n13 2 1 15 14 13 12 11 10 23 8 21 6 20\n16 2 1 15 14 13 12 11 10 9 22 7 6 5 19 20 21\n15 2 1 15 14 13 12 11 24 23 8 7 6 20 21 22\n20 2 1 15 14 13 12 11 10 9 8 7 6 5 4 18 19 20 21 22 23\n17 2 1 15 14 13 12 25 10 9 8 7 6 20 21 22 23 24\n10 2 1 15 14 27 26 11 10 24 25\n14 2 16 3 4 5 6 7 8 9 10 25 12 13 27\n18 2 1 15 14 13 12 11 10 9 8 7 21 22 23 24 25 26 27\n14 2 16 3 4 5 6 7 8 9 24 25 12 13 14\n14 3 2 1 15 14 13 12 11 10 23 22 7 20 5\n15 3 2 1 15 14 13 12 11 10 9 8 7 20 5 19\n16 3 2 1 15 14 13 12 25 10 23 8 7 6 5 19 20\n15 3 2 1 15 14 13 12 11 24 9 22 7 6 20 21\n16 3 2 1 15 14 13 12 11 10 9 8 7 6 20 21 22\n9 3 2 1 15 14 13 12 11 24\n22 3 2 1 15 14 13 12 11 10 9 8 7 6 5 4 18 19 20 21 22 23 24\n11 3 2 1 15 14 27 12 11 10 24 25\n16 3 2 1 15 14 27 12 11 10 9 8 22 23 24 25 26\n11 3 2 1 15 14 13 12 11 25 26 27\n15 3 2 16 17 4 5 6 7 8 9 10 11 12 13 14\n16 4 3 2 1 15 14 13 12 11 10 9 8 21 20 5 19\n17 4 3 2 1 15 14 13 12 11 24 9 8 7 6 5 19 20\n18 4 3 2 1 15 14 13 12 11 10 23 22 7 6 5 19 20 21\n13 4 3 2 1 15 14 13 26 25 10 23 8 22\n20 4 3 2 1 15 14 13 26 11 10 9 8 7 6 5 19 20 21 22 23\n13 4 3 2 1 15 14 13 26 25 10 9 23 24\n8 4 3 2 1 15 14 13 12\n14 4 3 2 16 17 18 5 6 7 8 23 24 25 26\n15 4 3 2 16 17 18 5 6 7 8 9 10 11 12 27\n16 4 3 2 16 17 18 5 6 7 8 9 10 25 26 27 14\n16 5 4 3 2 1 15 14 13 12 11 24 23 22 7 6 20\n13 5 4 3 2 1 15 14 13 12 11 10 23 8\n12 5 4 3 2 1 15 14 13 12 11 24 23\n11 5 4 3 2 1 15 14 13 12 25 10\n12 5 4 3 2 1 15 14 27 26 25 10 24\n14 5 4 3 2 16 17 18 19 6 7 22 9 10 11\n15 5 4 3 2 16 17 18 19 6 21 8 9 10 11 26\n16 5 4 3 2 16 17 18 19 6 7 8 9 10 25 26 13\n17 5 4 3 2 16 17 18 19 6 7 8 23 10 11 26 27 14\n14 6 5 4 3 2 1 15 14 13 12 25 10 23 22\n13 6 5 4 3 2 1 15 14 13 26 25 10 23\n16 6 5 4 3 2 1 15 14 13 12 11 10 9 8 22 23\n15 6 5 4 3 2 1 15 14 27 12 11 10 9 23 24\n19 6 5 4 3 2 16 17 18 19 20 7 22 9 24 25 12 13 27 26\n11 6 5 4 3 2 1 15 14 13 12 26\n17 6 5 4 3 2 16 17 18 19 20 7 8 9 10 11 12 13\n18 6 5 4 3 2 16 17 18 19 20 7 22 9 24 11 26 13 14\n14 7 6 5 4 3 2 1 15 14 13 12 25 24 9\n15 7 6 5 4 3 2 1 15 14 13 26 11 10 9 23\n16 7 6 5 4 3 2 1 15 14 13 26 25 10 9 23 24\n19 7 6 5 4 3 2 1 15 14 13 26 11 10 9 8 22 23 24 25\n19 7 6 5 4 3 2 16 17 18 19 20 21 8 9 24 11 26 13 27\n18 7 6 5 4 3 2 16 17 18 19 20 21 8 23 10 25 26 13\n19 7 6 5 4 3 2 16 17 18 19 20 21 8 9 10 11 12 13 14\n14 8 7 6 5 4 3 2 1 15 14 27 12 25 10\n15 8 7 6 5 4 3 16 1 15 14 13 12 11 10 24\n12 8 7 6 5 4 3 2 1 15 14 13 12\n19 8 7 6 5 4 3 16 1 15 14 13 12 11 10 9 23 24 25 26\n10 8 7 6 5 4 3 2 1 15 14\n20 8 7 6 5 4 3 2 16 17 18 19 20 21 22 9 10 25 12 13 14\n21 9 8 7 6 5 4 3 2 16 17 18 19 20 21 22 23 10 11 12 26 25\n18 9 8 7 6 5 4 3 2 16 17 18 19 20 21 22 23 10 25\n21 9 8 7 6 5 4 3 2 16 17 18 19 20 21 22 23 24 11 26 13 27\n15 9 8 7 6 5 4 3 2 1 15 14 13 12 26 27\n19 9 8 7 6 5 4 3 17 18 19 20 21 22 23 24 11 12 13 14\n19 10 9 8 7 6 5 4 3 2 16 17 18 19 20 21 22 23 24 11\n20 10 9 8 7 6 5 4 3 17 18 19 20 21 22 23 24 11 26 13 27\n12 10 9 8 7 6 5 18 17 2 1 15 14\n18 10 9 8 7 6 5 4 18 19 20 21 22 23 24 11 12 13 14\n14 11 10 9 8 7 6 5 4 17 16 1 15 14 13\n15 11 10 9 8 7 6 19 4 17 2 1 15 14 13 27\n23 11 10 9 8 7 6 5 4 3 2 16 17 18 19 20 21 22 23 24 25 26 27 14\n14 12 11 10 9 8 21 20 5 4 17 2 1 15 14\n13 12 11 10 9 8 7 6 5 4 17 16 1 15\n14 13 12 11 10 9 8 7 6 19 4 17 16 1 15\n",
        "29\n1 2 1\n2 3 3\n3 4 5\n4 5 7\n5 6 9\n6 7 11\n7 8 13\n8 9 15\n9 10 17\n10 11 19\n11 12 21\n12 13 23\n13 14 25\n14 15 27\n15 16 29\n1 16 4\n2 3 20\n3 4 38\n4 5 28\n5 6 12\n6 7 18\n7 8 34\n8 9 32\n9 10 48\n10 11 2\n11 12 14\n12 13 10\n13 14 22\n14 15 40\n1 1\n2 1 2\n3 1 2 3\n4 1 2 3 4\n5 1 2 3 4 5\n6 1 2 3 4 5 6\n7 1 2 3 4 5 6 7\n8 1 2 3 4 5 6 7 8\n9 1 2 3 4 5 6 7 8 9\n10 1 2 3 4 5 6 7 8 9 10\n11 1 2 3 4 5 6 7 8 9 10 11\n12 1 2 3 4 5 6 7 8 9 10 11 12\n13 1 2 3 4 5 6 7 8 9 10 11 12 13\n14 1 2 3 4 5 6 7 8 9 10 11 12 13 14\n15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15\n17 1 16 15 14 13 12 11 10 9 8 7 21 5 4 3 2 17\n16 1 16 15 14 13 12 11 10 24 23 22 21 5 19 3 18\n15 1 16 15 14 13 12 11 10 9 8 7 21 5 4 19\n16 1 16 15 14 13 12 11 10 9 8 22 21 5 4 19 20\n11 1 16 15 14 13 12 11 10 24 8 7\n18 1 16 15 14 13 12 11 10 24 23 7 6 5 4 19 20 21 22\n15 1 16 15 14 13 12 11 10 9 8 7 6 21 22 23\n16 1 16 15 14 13 27 11 10 9 8 7 6 21 22 23 24\n13 1 16 15 14 13 12 26 10 9 8 23 24 25\n16 1 16 15 14 13 12 11 10 9 8 7 22 23 24 25 26\n21 2 3 4 5 6 7 8 23 22 21 20 19 18 17 1 16 15 14 28 12 27\n26 1 16 15 14 13 12 11 10 9 8 7 6 5 4 3 18 19 20 21 22 23 24 25 26 27 28\n23 2 3 4 5 6 7 8 9 10 11 26 25 24 23 22 21 20 19 18 17 1 16 15\n14 2 3 4 5 6 7 8 24 25 11 27 13 14 15\n15 2 1 16 15 14 13 12 11 10 24 23 22 21 20 19\n14 2 1 16 15 14 13 12 11 10 24 23 22 6 20\n13 2 1 16 15 14 13 12 11 10 9 23 7 6\n18 2 1 16 15 14 13 12 26 25 24 8 7 6 5 4 19 20 21\n11 2 1 16 15 14 13 12 26 10 24 23\n10 2 1 16 15 14 13 12 11 10 9\n19 2 1 16 15 14 13 12 11 10 9 8 7 6 5 20 21 22 23 24\n24 2 1 16 15 14 13 12 11 10 9 8 7 6 5 4 3 18 19 20 21 22 23 24 25\n17 2 1 16 15 14 28 12 11 10 9 8 7 22 23 24 25 26\n22 2 1 16 15 29 13 12 11 10 9 8 7 6 5 20 21 22 23 24 25 26 27\n5 2 1 16 15 14\n26 2 1 16 15 14 13 12 11 10 9 8 7 6 5 4 19 20 21 22 23 24 25 26 27 28 29\n15 2 17 3 4 5 6 7 23 24 10 11 12 28 14 15\n15 3 2 1 16 15 14 13 12 11 10 9 8 7 6 20\n18 3 2 1 16 15 14 13 12 11 10 24 23 7 21 5 4 19 20\n17 3 2 1 16 15 14 13 12 11 25 9 8 22 6 5 20 21\n16 3 2 1 16 15 14 13 12 26 10 24 8 7 6 21 22\n11 3 2 1 16 15 14 13 27 11 25 9\n10 3 2 1 16 15 14 13 27 11 10\n21 3 2 1 16 15 14 13 12 26 10 9 8 7 6 5 20 21 22 23 24 25\n20 3 2 1 16 15 14 13 12 11 10 9 8 7 6 21 22 23 24 25 26\n13 3 2 1 16 15 29 13 12 11 10 25 26 27\n14 3 2 17 18 4 5 6 7 8 9 25 11 27 13\n15 3 2 17 18 4 5 6 7 8 9 10 26 12 28 29\n16 3 2 17 18 4 5 6 7 8 24 25 26 12 13 14 15\n17 4 3 2 1 16 15 14 13 12 11 10 24 23 7 6 5 20\n18 4 3 2 1 16 15 14 13 12 26 25 9 8 22 6 5 20 21\n13 4 3 2 1 16 15 14 13 12 11 10 9 8\n16 4 3 2 1 16 15 14 13 12 11 25 24 8 7 22 23\n11 4 3 2 1 16 15 14 13 27 26 10\n12 4 3 2 1 16 15 29 28 12 26 10 25\n9 4 3 2 1 16 15 14 28 12\n12 4 3 2 1 16 15 14 13 12 11 26 27\n23 4 3 2 1 16 15 14 13 12 11 10 9 8 7 6 21 22 23 24 25 26 27 28\n6 4 3 2 1 16 15\n17 4 3 2 17 18 19 5 6 7 8 24 25 11 12 13 14 15\n15 5 4 3 2 1 16 15 14 13 12 11 10 9 23 22\n16 5 4 3 2 1 16 15 14 13 27 11 10 9 23 7 22\n19 5 4 3 2 1 16 15 14 13 12 26 25 9 8 7 6 21 22 23\n20 5 4 3 2 1 16 15 14 13 12 11 10 9 8 7 6 21 22 23 24\n11 5 4 3 2 1 16 15 14 28 12 26\n22 5 4 3 2 1 16 15 14 28 27 11 10 9 8 7 6 21 22 23 24 25 26\n15 5 4 3 2 1 16 15 14 28 12 11 10 25 26 27\n16 5 4 3 2 17 18 19 20 6 7 8 9 10 26 12 28\n17 5 4 3 2 17 18 19 20 6 7 8 9 25 11 12 13 29\n18 5 4 3 2 17 18 19 20 6 7 8 9 25 11 27 28 14 15\n17 6 5 4 3 2 1 16 15 14 13 12 26 10 9 8 7 22\n14 6 5 4 3 2 1 16 15 14 13 12 26 10 24\n17 6 5 4 3 2 1 16 15 14 13 12 26 10 9 8 23 24\n14 6 5 4 3 2 1 16 15 29 28 12 11 10 25\n11 6 5 4 3 2 1 16 15 14 13 12\n10 6 5 4 3 2 1 16 15 14 13\n19 6 5 4 3 2 17 18 19 20 21 7 8 9 25 26 12 28 14 29\n18 6 5 4 3 2 17 18 19 20 21 7 8 9 10 11 12 13 29\n19 6 5 4 3 2 17 18 19 20 21 7 8 9 10 11 27 28 14 15\n15 7 6 5 4 3 2 1 16 15 14 13 27 26 10 24\n18 7 6 5 4 3 2 1 16 15 14 13 27 26 10 9 8 23 24\n15 7 6 5 4 3 2 1 16 15 14 28 12 11 10 25\n12 7 6 5 4 3 2 1 16 15 14 13 27\n11 7 6 5 4 3 2 1 16 15 29 28\n12 7 6 5 4 3 2 1 16 15 29 13 28\n13 7 6 5 4 3 2 1 16 15 14 13 28 29\n20 7 6 5 4 3 2 17 18 19 20 21 22 8 9 10 11 27 13 14 15\n15 8 7 6 5 4 3 2 1 16 15 14 28 27 11 10\n18 8 7 6 5 4 3 2 1 16 15 14 28 27 26 10 9 24 25\n13 8 7 6 5 4 3 2 1 16 15 14 28 12\n14 8 7 6 5 4 3 17 1 16 15 14 28 12 27\n21 8 7 6 5 4 3 2 17 18 19 20 21 22 23 9 25 11 12 13 14 29\n20 8 7 6 5 4 3 2 17 18 19 20 21 22 23 9 10 11 27 28 14\n21 8 7 6 5 4 3 2 17 18 19 20 21 22 23 24 25 26 27 13 14 15\n17 9 8 7 6 5 4 3 17 1 16 15 14 28 27 26 10 25\n16 9 8 7 6 5 4 3 17 1 16 15 14 28 27 11 26\n15 9 8 7 6 5 4 3 2 1 16 15 14 28 12 27\n18 9 8 7 6 5 4 3 2 1 16 15 14 13 12 11 26 27 28\n15 9 8 7 6 5 20 21 22 23 24 10 11 12 13 14\n22 9 8 7 6 5 4 3 2 17 18 19 20 21 22 23 24 10 11 27 13 14 15\n17 10 9 8 7 6 5 4 3 2 1 16 15 29 13 12 11 26\n16 10 9 8 7 6 5 4 19 20 21 22 23 24 25 26 27\n21 10 9 8 7 6 5 4 3 2 17 18 19 20 21 22 23 24 25 11 12 13\n18 10 9 8 7 6 5 4 19 20 21 22 23 24 25 11 12 13 14\n11 10 9 8 7 6 5 4 3 17 1 16\n17 11 10 9 8 7 6 5 4 3 17 1 16 15 14 13 12 27\n18 11 10 9 8 7 6 5 4 18 17 1 16 15 29 13 12 27 28\n23 11 10 9 8 7 6 5 4 3 2 17 18 19 20 21 22 23 24 25 26 12 13 14\n12 11 10 9 8 7 6 5 19 18 17 1 16\n15 12 11 10 9 8 7 6 5 19 3 2 1 16 15 14\n22 12 11 10 9 8 7 6 5 4 3 18 19 20 21 22 23 24 25 26 27 13 29\n13 12 11 10 9 8 7 6 5 19 3 2 1 16\n15 13 12 11 10 9 8 7 6 5 19 18 2 1 16 15\n14 13 12 11 10 9 8 22 21 20 19 3 2 1 16\n21 14 13 12 11 10 9 8 7 6 5 20 21 22 23 24 25 26 27 28 29 15\n",
    };

    int N; cin >> N;
    if(N >= answer.size()) cout << "-1\n";
    else cout << answer.at(N) << "\n";
    return 0;
}
0