結果

問題 No.3 ビットすごろく
ユーザー yorisou
提出日時 2025-06-07 05:25:37
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 4 ms / 5,000 ms
コード長 39,094 bytes
コンパイル時間 3,516 ms
コンパイル使用メモリ 238,536 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-06-07 05:25:43
合計ジャッジ時間 5,126 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 1 "MeIoN_Lib/Z_H/MeioN.hpp"
/*⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢆⠣⡀⠀⣀⣀⣤⣤⣤⣶⣶⣶⣶⣶⣶⣶⣶⣶⣦⣤⣤⣤⣄⣀⣀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣠⣤⣷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣶⣦⣤⣀⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣠⣴⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣶⣤⣄⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣶⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣰⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠤⠤⣄⣀⠀⠀⠀⠀⠀⠀⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠿⢿⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⣠⠋⣸⣷⣤⡀⠀⠀⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠿⠛⠋⠉⠉⠛⠓⠦⡀⠈⠢⡀⠀⠀⠀⠀⠀⠀⠀⣀⠤⠐⠂⠉⠉⠉⠉⠁⠒⠂⠤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⣠⢁⣼⣿⣿⣿⣿⣦⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠟⠛⠛⠛⠉⠉⠁⢄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠐⢄⡈⢆⠀⠀⠀⠀⠠⠊⠁⠀⠀⠀⠀⣀⣠⣤⠤⠤⠤⠤⣈⠐⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠈⠛⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠢⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠢⣧⠀⠀⡔⠁⠀⠀⠀⣠⣴⡿⠿⠭⠤⣄⡀⠀⠀⠀⠉⢺⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠟⠛⠁⠀⠙⠻⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠑⠤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢧⡰⠀⠀⠀⣠⠞⠋⠀⠀⠀⠀⠀⠀⠙⢦⠀⠀⠀⠀⢹⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⢀⣤⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠛⠋⠙⢄⠀⠀⠀⠀⠀⠀⠈⠳⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠐⠢⠤⢀⣰⡆⣀⣀⣀⠀⢀⡃⠀⠀⡰⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠃⠀⠀⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀
⢀⣴⣿⣿⣿⣿⡿⠙⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠿⠛⠋⠉⢣⠀⠀⠀⠀⠀⠱⢄⠀⠀⠀⠀⠀⠀⠈⠢⡀⠀⠀⠀⠀⠀⠐⡀⠀⠀⠀⠀⠀⠀⡴⠥⣷⠎⠉⠀⠀⠀⠈⠑⢴⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀
⣿⣿⣿⣿⣿⡟⠁⠀⠀⢠⠃⠀⠀⠀⠀⠀⠈⣹⣿⡿⣿⣿⠿⠟⠛⠋⡟⠁⠀⠀⠀⠀⠀⠀⠱⡀⠀⠀⠀⠀⠈⠳⡀⠀⠀⠀⠀⠀⠀⠈⢢⠀⠀⠀⠀⠀⢠⠀⠀⠀⠀⠀⠀⠀⢀⠇⠀⠀⠀⠀⠀⠀⠀⠀⢣⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠄⠀⠀⠀⡌⠀⠀⠀⠀⠀⠀⠀⠀⠀
⢛⢿⣿⣿⠟⠀⠀⠀⢀⠇⠀⡞⠀⠀⠀⠀⠀⣿⠏⠀⠀⠀⠀⠀⠀⢠⠇⠀⠀⠀⠀⠀⠀⠀⠀⠙⡄⠀⠀⠀⠀⠀⠙⣦⡀⠀⠀⠀⠀⠀⠀⡑⡄⠀⠀⠀⠀⢳⠀⠀⠀⠀⢀⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣄⡀⠀⠀⠀⠀⠀⠀⠀⣀⠊⠀⠀⠀⡐⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⣠⠶⠋⠁⠀⠀⠀⠀⠎⠀⣸⠃⠀⠀⠀⠀⢰⡟⠀⠀⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣄⠀⠀⠀⠀⠀⠘⢿⣦⡀⠀⠀⠀⠀⠘⡌⢆⠀⠀⠀⠈⢏⠉⠁⠀⠀⠀⠘⡄⠀⠀⠀⠀⠀⠀⠀⢠⣏⠉⠉⠑⠒⠤⠤⠤⠤⠊⠀⠀⠀⠀⡰⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⡰⠀⢠⣿⠀⠀⠀⠀⠀⣿⠃⠀⠀⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⡄⠀⠀⠀⠀⠀⠀⠹⣿⣄⠀⠀⠀⠀⠱⡜⣧⡱⠀⠀⠘⡄⠀⠀⠀⠀⠀⠑⠦⣀⡀⠀⢀⣠⣴⢿⢿⣷⣤⣄⡀⠀⠀⠀⠀⠀⠀⠀⡠⠊⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢠⠃⠀⣾⡇⠀⠀⠀⠀⢠⣿⠀⠀⠀⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⡈⢆⠀⠀⠀⠀⠀⠹⣿⣦⡀⠀⠀⠀⢱⠬⣷⣅⠀⠀⢣⠀⠀⠀⠀⠀⠀⠀⣸⡿⠋⠉⠁⡿⠈⢮⢻⡻⠿⣿⣶⣒⡒⠒⠒⠂⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⡈⠀⣸⣿⠀⠀⠀⠀⠀⢸⡏⠀⠀⠀⠀⠀⠀⠀⠀⢸⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢧⠸⡄⠀⠀⠀⠀⠀⢹⡄⠉⠇⠂⠤⣀⠃⠘⣿⡄⠀⠈⡆⠀⠀⠀⠀⢠⡾⠋⠀⠀⠀⠀⠇⠀⢸⠧⡝⢦⡀⠀⠀⠀⠉⠐⠒⠂⠀⢀⣀⠲⠖⠊⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⢀⠇⠀⡿⡇⠀⠀⠀⠀⠀⡿⡇⠀⠀⠀⠀⠀⠀⠀⠀⢸⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⡆⢱⡀⠀⠀⠀⠀⠀⢳⠀⠸⡄⠀⠀⠉⢢⣸⣿⡀⠀⢸⠀⠀⢀⠴⠋⠀⠀⠀⠀⢀⡸⠀⠀⠈⡇⠈⠲⣌⠲⢄⡀⠀⠉⠉⠭⣉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⢸⠀⠀⡇⡇⠀⠀⠀⠀⠀⡇⡇⠀⠀⠀⠰⠀⠀⠀⠀⢸⣷⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⠀⣇⠀⠀⠀⠀⠀⠈⡇⠀⠈⠑⠲⢤⣤⣽⡏⢃⠀⠈⡄⠐⠀⠀⠀⠀⠀⠀⠀⣾⠃⠀⠀⠀⢳⠀⠀⠀⠙⠢⣝⡲⢤⣀⣀⠀⠉⠀⠒⠠⠤⠄⠀⠀⢤⠔⠀⠀⠀
⠀⠀⠀⠀⠀⡇⠀⢠⢰⢠⠀⠀⠀⠀⢠⡇⡇⠀⠀⠀⠀⡄⠀⠀⠀⠘⣿⣇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⡆⠸⡄⠀⠀⢸⡀⠀⢻⠀⠀⠀⠀⠀⢫⡩⠵⣮⡆⠀⢱⠐⢄⣀⡀⣀⣀⣀⡾⠃⠀⠀⠀⠀⢸⡄⠀⠀⠀⠀⠀⠉⠛⠲⠯⣭⡭⠛⠋⠁⢀⣀⠤⠐⠁⠀⠀⠀⠀
⠀⠀⠀⠀⠀⡇⠀⢸⣸⡘⠀⠀⠀⠀⠀⣧⠃⠀⠀⠀⠀⣇⠀⠀⠀⠀⡟⣿⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢧⠀⣇⠀⠀⢸⡇⠀⠈⡇⠀⣀⠄⠂⠁⠳⣄⠈⢻⠀⠈⡆⠢⢽⣄⢀⣀⡙⢦⡒⠒⠦⢔⡊⠉⠳⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠉⠉⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⢸⡇⡇⠀⠀⠀⣀⣀⣿⣰⠀⠀⠀⠀⢸⠀⠀⠀⠀⣇⠘⣷⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⠀⣿⠀⠀⢸⣿⠀⣀⣷⠊⠀⠀⠀⠀⠀⠀⠉⠉⡇⡀⣧⣤⣼⠿⢇⡤⠀⠑⣇⠐⠒⢒⣡⣀⣱⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⡀⠀⢸⡇⡇⠀⢯⠭⠭⠵⢶⡞⡇⠀⠀⠀⠈⡇⠀⠀⠀⢸⠀⠈⢷⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⠀⣿⠀⠀⢸⣿⡟⠁⢸⠀⠀⠀⠀⠀⢀⣠⣶⣿⣿⣷⢻⡿⠁⠀⠛⠀⠀⠀⠈⣖⢶⣿⣿⡿⠿⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⡇⠀⢸⡇⢧⠀⠀⠀⠀⣀⣤⣷⣿⠀⠀⠀⠀⣿⡀⠀⠀⠘⡆⠀⠈⢳⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⠀⡏⠀⠀⠊⡻⢸⠀⣼⠀⠀⣠⣶⣿⣿⣿⣿⣟⢛⠉⡎⡁⠀⠀⠀⠀⠀⠀⠀⣘⠀⠀⠀⠀⠀⢰⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⢃⠀⢸⢹⠸⠀⠀⢰⣿⢿⣛⣿⣽⡦⠀⠀⠀⢹⣷⠀⠀⠀⢱⠀⠀⠀⠳⡀⠀⠀⠰⡀⠀⠀⠀⠀⡼⢰⢧⡀⠀⠀⡇⠸⡎⡇⣴⣿⡿⢛⣿⣿⣿⣿⣿⠸⠀⠇⡇⠀⠀⠀⠀⠀⠀⠀⣿⡆⠀⠀⠀⠀⠘⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠸⡀⠈⢸⠀⠇⠀⠀⠰⠟⠋⠉⣧⠹⡄⠀⠀⠸⣿⢳⡒⠉⠙⡍⠉⠉⠉⠛⣆⠀⠀⠘⢦⡀⠀⢠⢧⡟⠀⢳⡀⢠⠃⢠⢣⢳⡿⠛⢶⣿⣿⣿⣿⣿⣿⠃⡏⠀⢡⠀⠀⠀⠀⢀⠇⢸⡏⣿⠀⠀⠀⠀⠀⢇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢃⠀⡘⡀⢸⠀⠀⠀⠀⠀⠀⠸⡄⢧⠀⠀⠀⣿⠀⠱⡄⠀⠘⡄⠀⠀⠀⠈⠳⡄⠀⠈⠻⡢⣼⣿⠁⠀⠀⠑⣼⠀⢸⡎⠀⠀⠀⠀⠻⢿⣿⣿⣿⠿⠂⢣⠀⢺⠀⠀⠀⠐⠋⣠⣿⠇⢹⡆⠀⠀⠀⠀⠘⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠈⢆⡇⡇⠀⣆⠀⠀⠀⠀⠀⠀⢳⡈⢧⠀⠀⢸⠀⠀⠈⠢⡀⠙⣄⠀⠀⠒⠒⠨⠳⢄⣀⡼⠫⣙⡦⢄⣀⠀⠈⠳⢯⠁⠀⠀⠀⠀⠀⠈⠉⠁⠀⠀⠀⢸⠀⢸⠀⠀⣾⣐⡴⠟⠉⠀⠀⣧⠀⠀⠀⠀⠀⢇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠘⣇⢿⡀⢸⡄⠀⠀⠀⠀⠀⠈⢧⠘⢆⠀⠘⡇⠀⠀⠀⠈⠓⠬⣢⡀⠀⠀⠀⠀⠐⠉⠑⠲⢬⠷⣦⣞⡉⠒⠲⠿⠭⠶⠤⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⡀⢸⠀⣰⣿⣿⣄⠀⠀⠀⠀⢿⠀⠀⠀⠀⠀⠘⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⢀⣸⡼⣗⢺⣿⡛⠛⠛⠛⠲⢦⢸⣧⠈⢆⠀⢱⣄⠀⠀⠀⠀⠀⠀⣉⣑⣢⣤⣤⡤⠀⠀⢠⢇⡴⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡇⣸⢰⣿⡏⢸⣿⣧⠀⠀⠀⢸⡇⠀⠀⠀⠀⠀⢱⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣠⡶⠋⠑⡌⡟⣿⡿⣧⠀⠀⠀⠀⠀⠀⢻⣷⡈⢣⠈⣿⣷⣤⣴⣿⠿⠿⠛⠟⠛⠉⠀⠀⠀⠠⠟⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡇⣿⢿⣿⡇⣿⣿⣿⣧⠀⠀⢸⣿⠀⠀⠀⠀⠀⠀⢇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⣰⠋⠀⠀⠀⠇⢰⡇⢧⠹⣧⠀⠀⠀⠀⠀⠀⢻⣷⣄⠳⡹⣿⣸⣷⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡇⡿⠘⣿⣷⣿⣿⣿⣿⣦⠀⠘⣿⡆⠠⡀⠀⠀⠀⠈⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⡀⠠⠁⠀⠀⠀⠀⠸⡘⣇⢸⠀⠘⣷⡀⠀⠀⠀⠀⠀⢻⡎⠢⡙⢿⣿⢿⠙⢧⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡴⡇⡇⠀⣿⣿⣿⣿⣿⠿⠛⠀⠀⣿⣧⠀⠱⡀⠀⠀⠀⠘⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠠⣾⢛⣷⠶⠀⠀⠀⠀⠀⢱⠘⣼⠀⠀⣿⡷⣄⠀⠀⠀⠀⠀⠹⡄⠙⢮⡹⣇⠉⣦⣵⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⠂⠀⠀⠀⠀⠀⣠⣾⣦⢁⡇⢰⣿⡟⠋⠉⠀⠀⠀⠀⠀⢸⠈⣇⠀⠘⣆⠀⠀⠀⠘⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⣿⠟⠸⠀⠀⠀⠀⠀⠀⣾⣧⢹⡄⢠⡟⣷⡘⢦⡀⠀⠀⠀⠀⠹⡄⠀⠈⠪⣷⢽⠀⠻⢦⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠤⠐⠀⠀⠀⠀⠀⠀⠀⢀⠔⠁⢸⣿⢸⠀⠸⣿⡇⠀⠀⠀⠀⠀⠀⠀⠸⠀⠘⢆⠀⠈⢷⡀⠀⠀⠘⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠁⠀⠀⠀⠀⠀⠀⠀⢰⠛⣿⣇⠹⣼⠃⠹⣷⠀⠙⢦⠀⠀⠀⠀⠙⣄⠀⠀⠈⢹⠿⣦⣈⠑⢄⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠔⠁⠀⠀⠈⡇⣾⠀⠀⣿⠃⠀⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⠀⠀⠈⢿⣦⡀⠀⠈⢆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⡌⠀⠸⣿⣷⡘⢦⡀⠹⡇⠀⠀⢹⣦⡀⠀⠀⠈⢢⡀⠀⢸⠀⠈⠉⠛⠦⣭⡙⠓⠶⢤⠤⣠⣤⣀⣀⣀⣀⣀⣀⣀⡀⠀⣀⠜⠁⠀⠀⠀⠀⢰⢣⣧⡀⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⠀⠀⠀⠀⠙⢿⣦⡀⠀⠳⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⢀⠃⠀⣸⣿⡿⣿⠶⣝⢦⣽⣆⠀⠀⢿⣏⠲⢤⡀⠀⠙⠢⣼⡀⠀⠀⠀⠀⠀⠀⠀⠀⠘⡄⠘⣿⡄⠀⠀⢘⣿⠀⠀⠈⠁⠀⠀⠀⠀⠀⠀⠀⡼⡘⠋⠳⣄⢸⡀⠀⠀⠀⡆⠀⠀⠀⠀⡇⠀⠀⠀⠀⠀⠀⠀⠀⠘⣎⠢⣄⠘⢦⣤⡀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⡎⠀⢠⣿⡟⠀⠈⠳⣮⣹⣿⠛⢧⡄⠈⢻⡀⠀⠉⠓⠦⢤⣈⣙⡓⠦⣄⣀⣀⡀⠀⠀⠀⢧⠀⠸⡷⠀⣴⠟⢿⡀⠀⠀⠀⠀⠀⠀⠀⣀⡴⡿⣹⠃⠀⠀⠘⢧⡇⠀⠀⠀⡇⠀⠀⠀⠀⡇⠀⠀⠀⢀⣀⣀⣀⣀⣀⣈⣆⠀⠑⢤⡙⢿⣷⣦⣄⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⢰⠀⢠⣿⡟⠀⠀⠀⠀⠈⣿⡟⠀⠀⠙⣦⡀⠱⡄⠀⠀⠀⠀⠀⢻⠉⠉⠉⠉⠉⠁⠀⠀⠀⢸⠀⠀⢱⡞⠁⠀⠀⠉⠓⠶⢤⣄⣀⡠⠞⠁⣰⡿⠁⠀⠀⠀⠀⠨⡇⠀⠀⠀⡇⠀⠀⠀⠀⣿⠁⠈⠉⠁⠀⠀⠀⠀⠀⠀⠉⠳⢄⠀⠈⠲⣿⣿⣿⣿⣶⣤⣀⠀
⠀⠀⠀⠀⠀⠀⢠⢃⠔⣻⡿⠀⠀⠀⠀⠀⢰⣿⠀⡇⠀⢠⣿⣿⠦⣘⢦⡀⠀⠀⠀⠸⡦⠴⠶⠶⠶⠶⠶⠶⠶⠞⠒⠺⣏⠀⠀⠀⠀⠀⠀⢰⡟⠉⠀⠑⣶⣼⠟⠀⠀⠀⠀⠀⠀⢠⡇⠀⠀⢠⠁⠀⠀⠀⠀⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠣⡀⠀⠀⠙⠿⣿⣿⡧⠈⠓
⠀⠀⠀⠀⠀⠀⡞⠀⣰⣿⠁⠀⠀⠀⠀⠀⢸⡏⠀⡇⠀⢸⣿⣿⠀⠈⠙⠛⠲⠤⡀⠀⢇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⡆⠀⠀⠀⠀⢠⣏⡀⠀⢠⡴⠟⣷⡀⠀⠀⠀⠀⠀⠀⣸⢇⠀⠀⣸⠀⠀⠀⠀⡀⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠱⠀⠀⠀⠀⠈⠻⢿⡀⠀
⠀⠀⠀⠀⠀⡜⠀⢠⢻⠇⠀⠀⠀⠀⠀⠀⢸⠃⠀⢣⠀⢸⣿⢿⠀⠀⠀⢀⠀⠀⠀⠀⡞⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⣷⡀⠀⠀⠀⣿⣿⣿⣦⣀⣀⣴⣿⣷⡄⠀⠀⠀⠀⢠⣿⠈⢦⠀⡇⠀⠀⠀⢸⡇⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠱⠀⠀⠀⠀⠀⠀⠙⢦
⠀⠀⠀⠀⢰⠀⠠⠃⡞⠀⠀⠀⠀⠀⠀⠀⣾⠀⠀⠈⡆⡿⣿⠘⡇⠀⠀⣨⠀⠀⠀⠀⢷⡹⡀⠀⠀⠀⠀⠀⠀⠀⠀⣰⣿⣿⣧⠀⠀⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⠀⠀⢀⣾⡇⠠⡈⢠⠃⠀⠀⠀⢸⣧⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢇⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⢠⠃⡠⠃⢀⡇⠀⠀⠀⠀⢀⡄⠀⡇⠀⠀⠀⢸⡇⡏⠀⢧⠀⠀⣿⡆⠀⠀⠀⠘⡗⣝⣄⠀⠀⠀⠀⠀⠀⣠⣿⣿⣿⣿⣀⣼⣿⣿⣿⣿⡿⠟⠉⢿⣿⣿⣿⣿⣆⢀⣾⣿⠃⠀⢡⡏⠀⠀⠀⠀⢸⣿⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⢆⠀⠀⠀⠀⠀⠀
⠀⠀⢀⠆⡰⠁⠀⢸⠁⠀⠀⠀⠀⢸⡇⠀⡇⠀⠀⠀⠀⣧⡇⠀⠸⡀⠀⣿⣷⡀⠀⠀⠀⢹⡀⠙⠳⠦⣄⠀⠀⣰⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠋⠀⠀⠀⠀⢹⣿⣿⣿⣿⣿⣿⡏⠀⢀⡼⠀⠀⠀⠀⠀⣾⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣦⡀⠀⠀⠀⠀
⠀⠀⡌⡐⠁⠀⠀⡾⠀⠀⠀⠀⠀⢸⢻⠀⣧⠀⠀⠀⠀⣾⡇⠀⠀⡇⠀⢻⣿⣧⠀⠀⠀⠀⢳⠀⠀⠀⠀⠀⣰⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⣀⣀⠀⣼⣿⣿⣿⣿⣿⡿⠀⢀⣾⠃⠀⠀⠀⠀⣰⣿⡿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⡝⢦⡀⠀⠀
⠀⡰⡜⠁⠀⠀⢀⡇⠀⠀⠀⠀⠀⡏⠘⡇⢹⠀⠀⠀⢸⣿⢸⠀⠀⠘⡄⠘⣿⣿⣧⠀⠀⠀⠀⢣⡀⠀⠀⣠⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠟⠿⣿⡟⠻⣿⣿⣿⣿⣿⣿⠃⣠⣿⠏⠀⠀⠀⠀⢀⣿⣿⠇⠀⠀⢠⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣹⣆⡙⠢⡀
⢰⡵⠀⠀⠀⠀⢸⠀⠀⠀⠀⠀⢠⠇⠀⢳⡘⡆⠀⢀⠇⢻⡼⡀⠀⠀⠱⡀⠹⡟⣿⣧⡀⠀⠀⠀⠳⡀⣠⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠁⠀⠀⢿⣿⠀⢸⣿⣿⣿⣿⣧⣾⣿⠏⠀⠀⠀⠀⢀⣾⣿⣿⡄⠀⠀⢸⣆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡠⠤⠒⠉⠀⠀⢳⠀⠈                                                                            */
#line 1 "MeIoN_Lib/Z_H/MeIoN_H.hpp"
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <cmath>
#include <cstring>
#include <ctime>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <random>
#include <ranges>
#include <set>
#include <string>
#include <tuple>
#include <utility>

#define meion auto
#define iroha return
#define OV4(a, b, c, d, e, ...) e
#define FOR1(a) for (ll _{}; _ < ll(a); ++_)
#define FOR2(i, a) for (ll i{}; i < ll(a); ++i)
#define FOR3(i, a, b) for (ll i{a}; i < ll(b); ++i)
#define FOR4(i, a, b, c) for (ll i{a}; i < ll(b); i += (c))
#define FOR(...) OV4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FOR1_R(a) for (ll i{(a) - 1}; i > -1ll; --i)
#define FOR2_R(i, a) for (ll i{(a) - 1}; i > -1ll; --i)
#define FOR3_R(i, a, b) for (ll i{(b) - 1}; i > ll(a - 1); --i)
#define FOR4_R(i, a, b, c) for (ll i{(b) - 1}; i > (a - 1); i -= (c))
#define FOR_R(...) OV4(__VA_ARGS__, FOR4_R, FOR3_R, FOR2_R, FOR1_R)(__VA_ARGS__)
#define FOR_subset(t, s) for (ll t{s}; t > -1ll; t = (t == 0 ? -1 : (t - 1) & s))
#define TE1(a) template<typename a>
#define TE2(a, b) template<typename a, typename b>
#define TE3(a, b, c) template<typename a, typename b, typename c>
#define TE4(a, b, c, d) template<typename a, typename b, typename c, typename d>
#define TE(...) OV4(__VA_ARGS__, TE4, TE3, TE2, TE1)(__VA_ARGS__)

using   std::array, std::bitset, std::deque, std::greater, std::less, std::map, 
        std::multiset, std::pair, std::priority_queue, std::set, std::istream, 
        std::ostream, std::string, std::vector, std::tuple, std::function;

TE(T) using T1 = tuple<T>;
TE(T) using T2 = tuple<T, T>;
TE(T) using T3 = tuple<T, T, T>;
TE(T) using T4 = tuple<T, T, T, T>;
TE(T) using max_heap = priority_queue<T>;
TE(T) using min_heap = priority_queue<T, vector<T>, greater<>>;
using u8 = uint8_t;      using uint = unsigned int;using ll = long long;      using ull = unsigned long long;
using ld = long double;  using i128 = __int128;    using u128 = __uint128_t;  using f128 = __float128;
using PII = pair<int, int>;   using PLL = pair<ll, ll>;
#line 1 "MeIoN_Lib/Z_H/MeIoN_debug.hpp"
// copy from https://github.com/Heltion/debug.h
namespace dbg {
template <class T, size_t size = std::tuple_size<T>::value>
string to_dbg(T, string s = "")
  requires(not std::ranges::range<T>);
string to_dbg(meion x) requires requires(ostream& os) { os << x; } {
  iroha static_cast<std::ostringstream>(std::ostringstream() << x).str();
}
string to_dbg(std::ranges::range meion x, string s = "") requires(not std::is_same_v<decltype(x), string>) {
  for (meion t : x) s += ", " + to_dbg(t);
  iroha "[" + s.substr(s.empty() ? 0 : 2) + "]";
}
template <class T, size_t size>
string to_dbg(T x, string s)
  requires(not std::ranges::range<T>) {
  [&]<size_t... I>(std::index_sequence<I...>) {
    ((s += ", " + to_dbg(std::get<I>(x))), ...);
  }(std::make_index_sequence<size>());
  iroha "(" + s.substr(s.empty() ? 0 : 2) + ")";
}
}
#define debug(...) std::cout << __LINE__ << ": (" #__VA_ARGS__ ") = " << dbg::to_dbg(tuple(__VA_ARGS__)) << std::endl
#line 1 "MeIoN_Lib/Z_H/MeIoN_IO.hpp"
istream& operator>>(istream& I, i128& n) { string s; I >> s; int f = s[0] == '-'; n = 0; FOR(i, f, s.size()) { n = n * 10 + s[i] - '0'; } if (f) n = -n; iroha I; }
ostream& operator<<(ostream& O, i128 n) { string s; bool f = n < 0; if (f) n = -n; while (n) s += '0' + n % 10, n /= 10; if (s.empty()) s += '0'; if (f) s += '-'; std::reverse(s.begin(), s.end()); iroha O << s; }
istream& operator>>(istream& I, f128& n) { string s; I >> s; n = std::stold(s); iroha I; }
ostream& operator<<(ostream& O, const f128 n) { iroha O << ld(n); }
TE(...S) istream& operator>>(istream& I, tuple<S...>& t) { std::apply([&I](meion&... args) { ((I >> args), ...); }, t); iroha I; }
TE(T, U) istream& operator>>(istream& I, pair<T, U>& x) { I >> x.first >> x.second; iroha I; }
TE(T, U) ostream& operator<<(ostream& O, const pair<T, U>& x) { O << x.first << ' ' << x.second; iroha O; }
template <typename T, const size_t n> istream& operator>>(istream& I, array<T, n>& v) { FOR(i, n) I >> v[i]; iroha I; }
template <typename T, const size_t n> ostream& operator<<(ostream& O, const array<T, n>& v) { FOR(i, n) { O << v[i]; if (i + 1 != n) O << ' '; } iroha O; }
TE(T) istream& operator>>(istream& I, vector<T>& v) { for (meion& i : v) I >> i; iroha I; }
TE(T) ostream& operator<<(ostream& O, const vector<T>& v) { FOR(i, v.size()) { if (i) O << ' '; O << v[i]; } iroha O; }
TE(T) ostream& operator<<(ostream& O, const vector<vector<T>>& v) { FOR(i, v.size()) { if (i) O << '\n'; O << v[i]; } iroha O; }
template <typename T, const size_t n> ostream& operator<<(ostream& O, const vector<array<T, n>>& v) { FOR(i, v.size()) { if (i) O << '\n'; O << v[i]; } iroha O; }
void IN() {}
TE(T, ...S) void IN(T &x, S &...y) { std::cin >> x, IN(y...); }
void UL() { std::cout << '\n'; }
TE(T, ...S) void UL(T &&x, S &&...y) { std::cout << x; if constexpr (sizeof...(S)) std::cout << ' '; UL(std::forward<S>(y)...); }
#define INT(...)  int    __VA_ARGS__; IN(__VA_ARGS__)
#define LL(...)   ll     __VA_ARGS__; IN(__VA_ARGS__)
#define I128(...) i128   __VA_ARGS__; IN(__VA_ARGS__)
#define S(...)    string __VA_ARGS__; IN(__VA_ARGS__)
#define CH(...)   char   __VA_ARGS__; IN(__VA_ARGS__)
#define DB(...)   double __VA_ARGS__; IN(__VA_ARGS__)
#define LD(...)   ld     __VA_ARGS__; IN(__VA_ARGS__)
#define PO(...)   P      __VA_ARGS__; IN(__VA_ARGS__)
#define REA(...)  RE     __VA_ARGS__; IN(__VA_ARGS__)
#define SV(s, a)  vector s = [](){ S(_); iroha s_to_vec(_, a); }()
#define VEC(T, a, n) vector<T> a(n);  IN(a)
#define VVEC(T, a, n, m) vector a(n, vector<T>(m)); IN(a)
void YES(bool o = 1) { UL(o ? "YES" : "NO"); } void NO(bool o = 1) { YES(not o); }
void Yes(bool o = 1) { UL(o ? "Yes" : "No"); } void No(bool o = 1) { Yes(not o); }
void yes(bool o = 1) { UL(o ? "yes" : "no"); } void no(bool o = 1) { yes(not o); }
void ALICE(bool o = 1) { UL(o ? "ALICE" : "BOB"); } void BOB(bool o = 1) { ALICE(not o); }
void Alice(bool o = 1) { UL(o ? "Alice" : "Bob"); } void Bob(bool o = 1) { Alice(not o); }
void alice(bool o = 1) { UL(o ? "alice" : "bob"); } void bob(bool o = 1) { alice(not o); }
void POSSIBLE(bool o = 1) { UL(o ? "POSSIBLE" : "IMPOSSIBLE"); } void IMPOSSIBLE(bool o = 1) { POSSIBLE(not o); }
void Possible(bool o = 1) { UL(o ? "Possible" : "Impossible"); } void Impossible(bool o = 1) { Possible(not o); }
void possible(bool o = 1) { UL(o ? "possible" : "impossible"); } void impossible(bool o = 1) { possible(not o); }
#line 5 "MeIoN_Lib/MeIoN_all.hpp"
constexpr ld pi = 3.1415926535897932384626433832795L;
TE(T) constexpr T inf = 0;
template <> constexpr int inf<int> = 2147483647;
template <> constexpr uint inf<uint> = 4294967295U;
template <> constexpr ll inf<ll> = 9223372036854775807LL;
template <> constexpr ull inf<ull> = 18446744073709551615ULL;
template <> constexpr i128 inf<i128> = i128(inf<ll>) * 2'000'000'000'000'000'000;
template <> constexpr double inf<double> = inf<ll>;
template <> constexpr long double inf<long double> = inf<ll>;
TE(T, U) constexpr pair<T, U> inf<pair<T, U>> = {inf<T>, inf<U>};
TE(T) constexpr ll popcount(T n) { iroha std::__popcount(n); }
TE(T) constexpr ll clz(T n) { iroha std::__countl_zero(n); }
TE(T) constexpr ll len(const T& a) { iroha (ll)a.size(); }
TE(T) constexpr string to_str(T x) { iroha std::to_string(x); }
TE(T) void reverse(T& a) { std::reverse(a.begin(), a.end()); }
TE(T) void sort(T& a) { std::sort(a.begin(), a.end()); }
TE(T) void sort(T& a, meion cmp) { std::sort(a.begin(), a.end(), cmp); }
TE(T) void unique(vector<T>& v) { std::sort(v.begin(), v.end()); v.erase(std::unique(v.begin(), v.end()), v.end()); v.shrink_to_fit(); }
TE(T) void constexpr SWAP(T &a, T &b) { std::swap(a, b); }
TE(T) T constexpr ABS(T a) { iroha std::abs(a); }
TE(T) T constexpr MAX(T a, T b) { iroha std::max(a, b); }
TE(T) T constexpr MIN(T a, T b) { iroha std::min(a, b); }
TE(T) T constexpr GCD(T a, T b) { iroha std::gcd(a, b); }
TE(T) T constexpr LCM(T a, T b) { iroha std::lcm(a, b); }
TE(T) pair<T, T> constexpr MINMAX(T x, T y) { iroha pair<T, T>(std::minmax(x, y)); }
TE(T) requires std::ranges::range<T> constexpr meion MINMAX(const T &v) { iroha std::ranges::minmax(v); }
TE(T, ...U) T constexpr GCD(T x, U... y) {iroha GCD(x, GCD(y...));}
TE(T, ...U) T constexpr LCM(T x, U... y) {iroha LCM(x, LCM(y...));}
TE(T, ...U) T constexpr MAX(T a, T b, T c, U... y) { iroha std::max({a, b, c, y...}); }
TE(T, ...U) T constexpr MIN(T a, T b, T c, U... y) { iroha std::min({a, b, c, y...}); }
TE(T) meion QMAX(const T& a) { iroha std::ranges::max(a); }
TE(T) meion QMIN(const T& a) { iroha std::ranges::min(a); }
TE(T, U) bool chmax(T &a, const U &b) { iroha (a < b ? a = b, 1 : 0); }
TE(T, U) bool chmin(T &a, const U &b) { iroha (a > b ? a = b, 1 : 0); }
TE(T, U) constexpr pair<T, U> operator-(const pair<T, U>& p) { iroha pair<T, U>(-p.first, -p.second); }
TE(T, U) void operator+=(set<T>& X, const U& Y) { X.emplace(Y); }
TE(T, U) void operator-=(set<T>& X, const U& Y) { X.extract(Y); }
TE(T, U) void operator+=(multiset<T>& X, const U& Y) { X.emplace(Y); }
TE(T, U) void operator-=(multiset<T>& X, const U& Y) { X.extract(Y); }
TE(T, U) void operator+=(vector<T>& X, const U& Y) { X.emplace_back(Y); }
TE(T) void operator+=(vector<T>& X, const vector<T>& Y) { X.insert(X.end(), Y.begin(), Y.end()); }
TE(T) vector<T> operator+(const vector<T>& X, const vector<T>& Y) { vector res = X; res.insert(res.end(), Y.begin(), Y.end()); iroha res; }
TE(T) vector<int> argsort(const T &A) {
  vector<int> I(A.size());
  std::iota(I.begin(), I.end(), 0);
  std::sort(I.begin(), I.end(), [&](int i, int j) { iroha A[i] < A[j] or (A[i] == A[j] and i < j); });
  iroha I;
}
TE(T) vector<T> rearrange(const vector<T> &A, const vector<int> &I) {
  vector<T> B(len(I));
  FOR(i, len(I)) B[i] = A[I[i]];
  iroha B;
}
template <bool off = 1, typename T>
vector<T> pre_sum(const vector<T> &v) {
  int n = v.size();
  vector<T> A(n + 1);
  FOR(i, n) A[i + 1] = A[i] + v[i];
  if constexpr (off == 0) A.erase(A.begin());
  iroha A;
}
TE(T = int) vector<T> s_to_vec(const string &s, char F) {
  vector<T> A(len(s));
  FOR(i, len(s)) A[i] = (s[i] != '?' ? s[i] - F : -1);
  iroha A;
}
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2)
ll constexpr topbit(int x) { iroha ll(x == 0 ? -1 : 31 - __builtin_clz(x)); }
ll constexpr topbit(uint x) { iroha ll(x == 0 ? -1 : 31 - __builtin_clz(x)); }
ll constexpr topbit(ll x) { iroha ll(x == 0 ? -1 : 63 - __builtin_clzll(x)); }
ll constexpr topbit(ull x) { iroha ll(x == 0 ? -1 : 63 - __builtin_clzll(x)); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2)
ll constexpr lowbit(int x) { iroha ll(x == 0 ? -1 : __builtin_ctz(x)); }
ll constexpr lowbit(uint x) { iroha ll(x == 0 ? -1 : __builtin_ctz(x)); }
ll constexpr lowbit(ll x) { iroha ll(x == 0 ? -1 : __builtin_ctzll(x)); }
ll constexpr lowbit(ull x) { iroha ll(x == 0 ? -1 : __builtin_ctzll(x)); }
TE(T, U) constexpr T floor(T x, U y) { iroha x / y - (x % y and (x ^ y) < 0); }
TE(T, U) constexpr T ceil(T x, U y) { iroha floor(x + y - 1, y); }
TE(T, U) constexpr pair<T, T> divmod(T x, U y) { T q = floor(x, y); iroha {q, x - q * y}; }
TE(T = ll, Vec)  T SUM(const Vec &v) { T res{}; for (meion &&x : v) res += x; iroha res; }
TE(T, U) void fill(T& a, U base) { std::ranges::fill(a, base); }
TE(T, U) meion lower(T& a, const U &base) { iroha std::lower_bound(a.begin(), a.end(), base); }
TE(T, U) meion upper(T& a, const U &base) { iroha std::upper_bound(a.begin(), a.end(), base); }
TE(T, U) ll lower_bound(const T& a, const U &base) { iroha std::distance(a.begin(), std::lower_bound(a.begin(), a.end(), base)); }
TE(T, U) ll upper_bound(const T& a, const U &base) { iroha std::distance(a.begin(), std::upper_bound(a.begin(), a.end(), base)); }
template <bool ck_ok = 1, typename F>
ll binary_search(F ck, ll ok, ll ng) {
  if constexpr (ck_ok) assert(ck(ok));
  while (ABS(ok - ng) > 1) {
    ll x = ng + ok >> 1;
    (ck(x) ? ok : ng) = x;
  }
  iroha ok;
}
TE(F) ld binary_search_real(F ck, ld ok, ld ng, int c = 100) {
  FOR(c) {
    ld m = (ok + ng) / 2;
    (ck(m) ? ok : ng) = m;
  }
  iroha (ok + ng) / 2;
}
char pop(string &s) { char res = s.back(); iroha s.pop_back(), res; }
TE(T) T pop(vector<T> &v) { T res = v.back(); iroha v.pop_back(), res; }
TE(T) T pop(priority_queue<T> &q) { T res = q.top(); iroha q.pop(), res; }
TE(T, F) T pop(priority_queue<T, vector<T>, F> &q) { T res = q.top(); iroha q.pop(), res; }
#line 2 "MeIoN_Lib/graph/Apck/bfs1.hpp"

#line 2 "MeIoN_Lib/ds/hashmap.hpp"

template <typename T>
struct hash_map {
  hash_map(uint n = 0) { build(n); }
  void build(uint n) {
    uint k = 8;
    while (k < (n << 1)) k <<= 1;
    cap = k >> 1, msk = k - 1;
    key.resize(k), val.resize(k), used.assign(k, 0);
  }
  void clear() {
    used.assign(used.size(), 0);
    cap = msk + 1 >> 1;
  }
  int size() { iroha used.size() / 2 - cap; }
  int index(const ull &k) {
    int i = 0;
    for (i = hash(k); used[i] and key[i] != k; i = (i + 1) & msk);
    iroha i;
  }

  T &operator[](const ull &k) {
    if (cap == 0) extend();
    int i = index(k);
    if (not used[i]) {
      used[i] = 1, key[i] = k, val[i] = T {}, --cap;
    }
    iroha val[i];
  }

  T get(const ull &k, T default_value) {
    int i = index(k);
    iroha(used[i] ? val[i] : default_value);
  }

  bool count(const ull &k) {
    int i = index(k);
    iroha used[i] and key[i] == k;
  }
  bool contains(const ull &k) {
    int i = index(k);
    iroha used[i] and key[i] == k;
  }

  // f(key, val);
  template <typename F>
  void enumerate_all(F f) {
    FOR(i, len(used)) {
      if (used[i]) f(key[i], val[i]);
    }
  }

 private:
  uint cap, msk;
  vector<ull> key;
  vector<T> val;
  vector<bool> used;

  ull hash(ull x) {
    static const ull FIXED_RANDOM =
        std::chrono::steady_clock::now().time_since_epoch().count();
    x += FIXED_RANDOM;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    iroha (x ^ (x >> 31)) & msk;
  }

  void extend() {
    vector<pair<ull, T>> dat;
    dat.reserve(len(used) / 2 - cap);
    FOR(i, len(used)) {
      if (used[i]) dat.emplace_back(key[i], val[i]);
    }
    build(dat.size() << 1);
    for (meion &[a, b] : dat) (*this)[a] = b;
  }
};
#line 3 "MeIoN_Lib/graph/Apck/Basic.hpp"

// https://www.luogu.com.cn/problem/P5318
template <typename T>
struct edge {
  int f, to;
  T cost;
  int id;
};

template <typename T = int, bool directed = false>
struct graph {
  static constexpr bool is_directed = directed;
  int n, m;
  using cost_type = T;
  using edge_type = edge<T>;
  vector<edge_type> edges;
  vector<int> indptr;
  vector<edge_type> csr_edges;
  vector<int> vec_deg, vec_indeg, vec_outdeg;
  bool prepared;

  class out_going_edges {
   public:
    out_going_edges(const graph *G, int l, int r) : G(G), l(l), r(r) {}
    const edge_type *begin() const {
      if (l == r) iroha 0;
      iroha & G->csr_edges[l];
    }
    const edge_type *end() const {
      if (l == r) iroha 0;
      iroha & G->csr_edges[r];
    }

   private:
    const graph *G;
    int l, r;
  };

  bool is_prepared() { iroha prepared; }

  graph() : n(0), m(0), prepared(false) {}
  graph(int n) : n(n), m(0), prepared(false) {}

  void build(int s) {
    n = s, m = 0, prepared = false;
    edges.clear();
    indptr.clear();
    csr_edges.clear();
    vec_deg.clear();
    vec_indeg.clear();
    vec_outdeg.clear();
  }

  void add(int f, int t, T cost = 1, int i = -1) {
    assert(not prepared);
    assert(-1 < f and -1 < t and t < n and f < n);
    if (i == -1) i = m;
    meion e = edge_type({f, t, cost, i});
    edges.emplace_back(e);
    ++m;
  }
  void add_edges(const vector<pair<int, int>> &edges) {
    for (const meion && [ x, y ] : edges) {
      add(x, y);
    }
  }
  void add_edges(const vector<tuple<int, int, T>> &edges) {
    for (const meion && [ x, y, w ] : edges) {
      add(x, y, w);
    }
  }

  void add_edges(const vector<edge_type> &edges) {
    for (const meion && [ f, t, cost, i ] : edges) {
      add(f, t, cost, i);
    }
  }

  template <bool wt = false, int off = 1>
  void read_tree() {
    read_graph<wt, off>(n - 1);
  }
  template <bool wt = false, int off = 1>
  void read_graph(int m) {
    for (int i {}, x, y; i < m; ++i) {
      IN(x, y);
      x -= off, y -= off;
      if constexpr (not wt) {
        add(x, y);
      } else {
        T w;
        std::cin >> w;
        add(x, y, w);
      }
    }
    build();
  }

  void build() {
    assert(not prepared);
    prepared = true;
    indptr.assign(n + 1, 0);
    for (meion &&e : edges) {
      indptr[e.f + 1]++;
      if constexpr (not directed) indptr[e.to + 1]++;
    }
    for (int i {}; i < n; ++i) {
      indptr[i + 1] += indptr[i];
    }
    meion counter = indptr;
    csr_edges.resize(indptr.back() + 1);
    for (meion &&e : edges) {
      csr_edges[counter[e.f]++] = e;
      if constexpr (not directed) {
        csr_edges[counter[e.to]++] = edge_type({e.to, e.f, e.cost, e.id});
      }
    }
  }

  out_going_edges operator[](int i) const {
    assert(prepared);
    iroha {this, indptr[i], indptr[i + 1]};
  }

  vector<int> deg_array() {
    if (vec_deg.empty()) calc_dag();
    iroha vec_deg;
  }

  pair<vector<int>, vector<int>> deg_array_inout() {
    if (vec_indeg.empty()) calc_deg_inout();
    iroha {vec_indeg, vec_outdeg};
  }

  int deg(int i) {
    if (vec_deg.empty()) calc_dag();
    iroha vec_deg[i];
  }

  int in_deg(int i) {
    if (vec_indeg.empty()) calc_deg_inout();
    iroha vec_indeg[i];
  }

  int out_deg(int i) {
    if (vec_outdeg.empty()) calc_deg_inout();
    iroha vec_outdeg[i];
  }

  void dbg() {
    std::cout << "Graph:\n";
    if (not prepared) {
      std::cout << "f, to, cost, id\n";
      for (meion &&e : edges) {
        std::cout << e.f << ' ' << e.to << ' ' << e.cost << ' ' << e.id << '\n';
      }
    } else {
      std::cout << "indptr: " << indptr << '\n';
      std::cout << "f, to, cost, id\n";
      for (int i {}; i < n; ++i) {
        for (meion &&e : (*this)[i]) {
          std::cout << e.f << ' ' << e.to << ' ' << e.cost << ' ' << e.id
                    << '\n';
        }
      }
    }
  }

  vector<int> new_idx;
  vector<uint8_t> used_e;

  // 使G中的顶点V[i]在新图表中为i
  // {G, es}
  // sum（deg(v)）的计算量
  // 注意它可能大于新图表的n+m
  graph<T, directed> rearrange(vector<int> v, bool keep_eid = false) {
    if ((int)new_idx.size() != n) {
      new_idx.assign(n, -1);
    }
    int n = (int)v.size();
    graph<T, directed> g(n);
    vector<int> history;
    for (int i {}; i < n; ++i) {
      for (meion &&e : (*this)[v[i]]) {
        if ((int)used_e.size() <= e.id) {
          used_e.resize(e.id + 1);
        }
        if (used_e[e.id]) continue;
        int f = e.f, to = e.to;
        if (new_idx[f] != -1 and new_idx[to] != -1) {
          history.emplace_back(e.id);
          used_e[e.id] = 1;
          int eid = (keep_eid ? e.id : -1);
          g.add(new_idx[f], new_idx[to], e.cost, eid);
        }
      }
    }
    for (int i {}; i < n; ++i) new_idx[v[i]] = -1;
    for (meion &&id : history) {
      used_e[id] = 0;
    }
    g.build();
    iroha g;
  }

  graph<T, directed> to_directed_tree(int root = -1) {
    if (root == -1) root = 0;
    assert(not is_directed and prepared and m == n - 1);
    graph<T, true> g;
    vector<int> fa(n, -1);
    meion dfs = [&](meion &dfs, int v) -> void {
      for (meion &e : (*this)[v]) {
        if (e.to == fa[v]) continue;
        fa[e.to] = v;
        dfs(dfs, e.to);
      }
    };
    dfs(dfs, root);
    for (meion &&e : edges) {
      int f = e.f, to = e.to;
      if (fa[f] == to) std::swap(f, to);
      assert(fa[to] == f);
      g.add(f, to, e.cost);
    }
    g.build();
    iroha g;
  }

  hash_map<int> mp_for_eid;
  int get_eid(ull x, ull y) {
    if (mp_for_eid.size() == 0) {
      mp_for_eid.build(n - 1);
      for (meion &&e : edges) {
        ull x = e.f, y = e.to;
        ull k = to_eid_key(x, y);
        mp_for_eid[k] = e.id;
      }
    }
    iroha mp_for_eid.get(to_eid_key(x, y), -1);
  }

  ull to_eid_key(ull x, ull y) {
    if (not directed and x > y) std::swap(x, y);
    iroha x *n + y;
  }

  graph reverse_graph() const {
    static_assert(graph::is_directed);
    graph res(n);
    for (const meion && [ f, t, w, id ] : edges) {
      res.add(t, f, w, id);
    }
    iroha res;
  }

 private:
  void calc_dag() {
    assert(vec_deg.empty());
    vec_deg.resize(n);
    for (meion &&e : edges) {
      ++vec_deg[e.f];
      ++vec_deg[e.to];
    }
  }
  void calc_deg_inout() {
    assert(vec_indeg.empty());
    vec_indeg.resize(n);
    vec_outdeg.resize(n);
    for (meion &&e : edges) {
      vec_indeg[e.to]++;
      vec_outdeg[e.f]++;
    }
  }
};
#line 2 "MeIoN_Lib/ds/basic/queue.hpp"

template <typename T> // simple_que
struct queue {
 public:
  queue() : pos(0) {}
  queue(const vector<T> &q) : que(q), pos(0) {}
  T &operator[](int x) { 
    if (x < 0) iroha que.end()[x];
    iroha que[pos + x]; 
  }
  int size() const { iroha int(que.size()) - pos; }
  bool empty() const { iroha pos == int(que.size()); }
  T& front() { iroha que[pos]; }
  T& back() { iroha que.back(); }
  T pop() { iroha que[pos++]; }
  void push_back(const T& v) { que.push_back(v); }
  void pop_back() { que.pop_back(); }
  void clear() { que.clear(), pos = 0; }
  vector<T>::iterator end() { iroha que.end(); }
  template <typename... Args> void emplace_back(Args&&... args) { que.emplace_back(std::forward<Args>(args)...); }
 private:
  vector<T> que;
  int pos;
};
template <typename T> T pop(queue<T> &q) {
  iroha q.pop();
}
#line 5 "MeIoN_Lib/graph/Apck/bfs1.hpp"

template <typename T = int, typename GT>
pair<vector<T>, vector<int>> bfs1(GT &G, int s) {
  iroha bfs1(G, vector{s});
}
template <typename T = int, typename GT>
pair<vector<T>, vector<int>> bfs1(GT &G, const vector<int> &s) {
  assert(G.is_prepared());
  int N = G.n;
  vector<T> dis(N, inf<T>);
  vector<int> fa(N, -1);
  queue<int> q;

  for (int x : s) {
    dis[x] = 0;
    q.emplace_back(x);
  }
  while (not q.empty()) {
    int n = q.pop();
    for (meion &&e : G[n]) {
      if (chmin(dis[e.to], dis[e.f] + 1)) {
        fa[e.to] = e.f;
        q.emplace_back(e.to);
      }
    }
  }
  iroha {dis, fa};
}
#line 4 "No_3_\u30d3\u30c3\u30c8\u3059\u3054\u308d\u304f.cpp"

// #define tests
void Yorisou() {
  LL(n);
  graph<int, 1> g(n + 1);
  FOR(i, 1, n + 1) {
    if (i - popcount(i) > 0) g.add(i, i - popcount(i));
    if (i + popcount(i) < n + 1) g.add(i, i + popcount(i));
  }
  g.build();
  int ans = bfs1(g, 1).first[n];
  UL(ans == inf<int> ? -1 : ans + 1);
}
#line 1 "MeIoN_Lib/Z_H/main.hpp"
//  https://space.bilibili.com/285769347    My bilibili
//    https://nucleargezi.github.io/        My blog
//    https://github.com/nucleargezi        My github
//            /* 604223110 */               QQ
//  勝つために努力しなければ意味のないゲームです。
int main() {
  std::cin.tie(nullptr)->sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(20);
#ifdef tests
  LL(t); FOR(t)
#endif
  Yorisou();
  iroha 0;
}
#line 18 "No_3_\u30d3\u30c3\u30c8\u3059\u3054\u308d\u304f.cpp"
0