結果
| 問題 |
No.4 おもりと天秤
|
| コンテスト | |
| ユーザー |
 yorisou
|
| 提出日時 | 2025-06-07 05:29:05 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 5,000 ms |
| コード長 | 40,139 bytes |
| コンパイル時間 | 2,726 ms |
| コンパイル使用メモリ | 227,132 KB |
| 実行使用メモリ | 6,272 KB |
| 最終ジャッジ日時 | 2025-06-07 05:29:09 |
| 合計ジャッジ時間 | 3,869 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 23 |
コンパイルメッセージ
MeIoN_Lib/ds/basic/bit_vec.hpp: In member function ‘bit_vec::T& bit_vec::operator>>=(ll)’:
MeIoN_Lib/ds/basic/bit_vec.hpp:122:25: warning: narrowing conversion of ‘(64 - x)’ from ‘ll’ {aka ‘long long int’} to ‘ull’ {aka ‘long long unsigned int’} [-Wnarrowing]
ソースコード
#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/ds/basic/bit_vec.hpp"
// https://codeforces.com/contest/914/problem/F
// https://yukicoder.me/problems/no/142
struct bit_vec {
using T = bit_vec;
int N;
vector<ull> dat;
// x で埋める
bit_vec(int N = 0, int x = 0) : N(N) {
assert(x == 0 || x == 1);
ull v = (x == 0 ? 0 : -1);
dat.assign((N + 63) >> 6, v);
if (N) dat.back() >>= (64 * len(dat) - N);
}
int size() const { iroha N; }
void resize(int size) {
dat.resize((size + 63) >> 6);
int remainingBits = size & 63;
if (remainingBits != 0) {
ull mask = (1ull << remainingBits) - 1;
dat.back() &= mask;
}
N = size;
}
void append(int idx, bool b) {
assert(N == idx);
resize(idx + 1), (*this)[idx] = b;
}
static T from_string(string &S) {
int N = len(S);
T ANS(N);
FOR(i, N) ANS[i] = (S[i] == '1');
iroha ANS;
}
class Proxy {
public:
Proxy(vector<ull> &d, int i) : dat(d), index(i) {}
operator bool() const { iroha(dat[index >> 6] >> (index & 63)) & 1; }
Proxy &operator=(ull value) {
dat[index >> 6] &= ~(ull(1) << (index & 63));
dat[index >> 6] |= (value & 1) << (index & 63);
iroha *this;
}
void flip() {
dat[index >> 6] ^= (ull(1) << (index & 63)); // XOR to flip the bit
}
friend void SWAP(Proxy a, Proxy b) {
bool ta = a;
bool tb = b;
a = tb;
b = ta;
}
private:
vector<ull> &dat;
int index;
};
Proxy operator[](int i) { iroha Proxy(dat, i); }
bool operator==(const T &p) const {
assert(N == p.N);
FOR(i, len(dat)) if (dat[i] != p.dat[i]) iroha false;
iroha true;
}
bool operator<(const T &p) const {
assert(N == p.N);
FOR(i, len(dat)) if (dat[i] != p.dat[i]) iroha dat[i] < p.dat[i];
iroha false;
}
bool operator>(const T &p) const {
assert(N == p.N);
FOR(i, len(dat)) if (dat[i] != p.dat[i]) iroha dat[i] > p.dat[i];
iroha false;
}
void move_L(ll x) {
if (not x) iroha;
FOR(i, len(dat) - x) { dat[i] = dat[i + x]; }
FOR(i, MAX(0ll, len(dat) - x), len(dat)) { dat[i] = 0; }
}
void move_R(ll x) {
if (not x) iroha;
FOR_R(i, x, len(dat)) { dat[i] = dat[i - x]; }
FOR_R(i, MIN(x, (ll)len(dat))) { dat[i] = 0; }
}
T &operator<<=(ll x) {
if (x < 0) {
*this >>= -x;
iroha *this;
}
move_R(x / 64);
x %= 64;
ull tp = 0, pos = 64 - x;
FOR(i, 1, x + 1) tp |= 1ull << (64 - i);
ull lst = 0;
FOR(i, len(dat)) {
ull tp_lst {(dat[i] & tp) >> pos};
dat[i] <<= x;
dat[i] |= lst;
lst = tp_lst;
}
resize(N);
iroha *this;
}
T &operator>>=(ll x) {
if (x < 0) {
*this <<= -x;
iroha *this;
}
move_L(x / 64);
x %= 64;
ull tp {(1ull << x) - 1};
ull lst {}, pos {64 - x};
FOR_R(i, len(dat)) {
ull tp_lst = (dat[i] & tp) << pos;
dat[i] >>= x;
dat[i] |= lst;
lst = tp_lst;
}
iroha *this;
}
T operator<<(const ll &x) const {
T res = *this;
res <<= x;
iroha res;
}
T operator>>(const ll &x) const {
T res = *this;
res >>= x;
iroha res;
}
T &operator&=(const T &p) {
assert(N == p.N);
FOR(i, len(dat)) dat[i] &= p.dat[i];
iroha *this;
}
T &operator|=(const T &p) {
assert(N == p.N);
FOR(i, len(dat)) dat[i] |= p.dat[i];
iroha *this;
}
T &operator^=(const T &p) {
assert(N == p.N);
FOR(i, len(dat)) dat[i] ^= p.dat[i];
iroha *this;
}
T operator&(const T &p) const { iroha T(*this) &= p; }
T operator|(const T &p) const { iroha T(*this) |= p; }
T operator^(const T &p) const { iroha T(*this) ^= p; }
T operator~() const {
T p = (*this);
p.flip_range(0, N);
iroha p;
}
void set_minus_inplace(T &other) {
assert(N == other.N);
FOR(i, len(dat)) dat[i] = dat[i] & (~other.dat[i]);
}
T set_minus(T other) {
assert(N == other.N);
FOR(i, len(dat)) other.dat[i] = dat[i] & (~other.dat[i]);
iroha other;
}
int count() {
int ans = 0;
for (ull val : dat) ans += popcount(val);
iroha ans;
}
int dot(T &p) {
assert(N == p.N);
int ans = 0;
FOR(i, len(dat)) ans += popcount(dat[i] & p.dat[i]);
iroha ans;
}
int next(int i) {
chmax(i, 0);
if (i >= N) iroha N;
int k = i >> 6;
{
ull x = dat[k];
int s = i & 63;
x = (x >> s) << s;
if (x) iroha (k << 6) | lowbit(x);
}
FOR(idx, k + 1, len(dat)) {
if (dat[idx] == 0) continue;
iroha (idx << 6) | lowbit(dat[idx]);
}
iroha N;
}
int prev(int i) {
chmin(i, N - 1);
if (i <= -1) iroha - 1;
int k = i >> 6;
if ((i & 63) < 63) {
ull x = dat[k];
x &= (ull(1) << ((i & 63) + 1)) - 1;
if (x) iroha(k << 6) | topbit(x);
--k;
}
FOR_R(idx, k + 1) {
if (dat[idx] == 0) continue;
iroha(idx << 6) | topbit(dat[idx]);
}
iroha - 1;
}
bit_vec range(int L, int R) {
assert(L <= R);
bit_vec p(R - L);
int rm = (R - L) & 63;
FOR(rm) {
p[R - L - 1] = bool((*this)[R - 1]);
--R;
}
int n = (R - L) >> 6;
int hi = L & 63;
int lo = 64 - hi;
int s = L >> 6;
if (hi == 0) {
FOR(i, n) { p.dat[i] ^= dat[s + i]; }
} else {
FOR(i, n) { p.dat[i] ^= (dat[s + i] >> hi) ^ (dat[s + i + 1] << lo); }
}
iroha p;
}
bit_vec slice(int L, int R) { iroha range(L, R); }
int count_range(int L, int R) {
assert(L <= R);
int cnt = 0;
while ((L < R) and (L & 63)) cnt += (*this)[L++];
while ((L < R) and (R & 63)) cnt += (*this)[--R];
int l = L >> 6, r = R >> 6;
FOR(i, l, r) cnt += popcount(dat[i]);
iroha cnt;
}
// [L,R) 赋为 p
void assign_to_range(int L, int R, bit_vec &p) {
assert(p.N == R - L);
int a = 0, b = p.N;
while (L < R and (L & 63)) {
(*this)[L++] = bool(p[a++]);
}
while (L < R and (R & 63)) {
(*this)[--R] = bool(p[--b]);
}
// p[a:b] を [L:R] に
int l {L >> 6}, r {R >> 6};
int s {a >> 6}, t {b >> t};
int n {r - l};
if (not(a & 63)) {
FOR(i, n) dat[l + i] = p.dat[s + i];
} else {
int hi = a & 63;
int lo = 64 - hi;
FOR(i, n) dat[l + i] = (p.dat[s + i] >> hi) | (p.dat[1 + s + i] << lo);
}
}
// [L,R) 异或 p
void xor_to_range(int L, int R, bit_vec &p) {
assert(p.N == R - L);
int a = 0, b = p.N;
while (L < R and (L & 63)) {
dat[L >> 6] ^= ull(p[a]) << (L & 63);
++a, ++L;
}
while (L < R and (R & 63)) {
--b, --R;
dat[R >> 6] ^= ull(p[b]) << (R & 63);
}
int l = L >> 6, r = R >> 6;
int s = a >> 6, t = b >> t;
int n = r - l;
if (!(a & 63)) {
FOR(i, n) dat[l + i] ^= p.dat[s + i];
} else {
int hi = a & 63;
int lo = 64 - hi;
FOR(i, n)
dat[l + i] ^= (p.dat[s + i] >> hi) | (p.dat[1 + s + i] << lo);
}
}
// 用于矩阵基本变换的方法
// p は [i:N) にしかないとして p を xor する
void xor_suffix(int i, bit_vec &p) {
assert(N == p.N and 0 <= i and i < N);
FOR(k, i / 64, len(dat)) { dat[k] ^= p.dat[k]; }
}
// [L,R) and p
void and_to_range(int L, int R, bit_vec &p) {
assert(p.N == R - L);
int a = 0, b = p.N;
while (L < R and (L & 63)) {
if (!p[a]) (*this)[L] = 0;
a++, L++;
}
while (L < R and (R & 63)) {
--b, --R;
if (!p[b]) (*this)[R] = 0;
}
// p[a:b] を [L:R] に
int l = L >> 6, r = R >> 6;
int s = a >> 6, t = b >> t;
int n = r - l;
if (!(a & 63)) {
FOR(i, n) dat[l + i] &= p.dat[s + i];
} else {
int hi = a & 63;
int lo = 64 - hi;
FOR(i, n)
dat[l + i] &= (p.dat[s + i] >> hi) | (p.dat[1 + s + i] << lo);
}
}
// [L,R) 或 p
void or_to_range(int L, int R, bit_vec &p) {
assert(p.N == R - L);
int a = 0, b = p.N;
while (L < R and (L & 63)) {
dat[L >> 6] |= ull(p[a]) << (L & 63);
++a, ++L;
}
while (L < R and (R & 63)) {
--b, --R;
dat[R >> 6] |= ull(p[b]) << (R & 63);
}
int l = L >> 6, r = R >> 6;
int s = a >> 6, t = b >> t;
int n = r - l;
if (!(a & 63)) {
FOR(i, n) dat[l + i] |= p.dat[s + i];
} else {
int hi = a & 63;
int lo = 64 - hi;
FOR(i, n)
dat[l + i] |= (p.dat[s + i] >> hi) | (p.dat[1 + s + i] << lo);
}
}
// 用于矩阵初等变换的方法
// 假设 p 只存在于 [i:N) 范围内，对该范围进行按位或(p)操作
void or_suffix(int i, bit_vec &p) {
assert(N == p.N and 0 <= i and i < N);
FOR(k, i / 64, len(dat)) { dat[k] |= p.dat[k]; }
}
// [L, R) 区间修改为 1
void set_range(int L, int R) {
while (L < R and (L & 63)) {
set(L++);
}
while (L < R and (R & 63)) {
set(--R);
}
FOR(i, L >> 6, R >> 6) dat[i] = ull(-1);
}
// [L, R) 区间修改为 0
void reset_range(int L, int R) {
while (L < R and (L & 63)) {
reset(L++);
}
while (L < R and (R & 63)) {
reset(--R);
}
FOR(i, L >> 6, R >> 6) dat[i] = ull(0);
}
// [L,R) 翻转
void flip_range(int L, int R) {
while (L < R and (L & 63)) {
flip(L++);
}
while (L < R and (R & 63)) {
flip(--R);
}
FOR(i, L >> 6, R >> 6) dat[i] ^= ull(-1);
}
// bitset に仕様を合わせる
void set(int i) { (*this)[i] = 1; }
void reset(int i) { (*this)[i] = 0; }
void flip(int i) { (*this)[i].flip(); }
void set() {
fill(dat, ull(-1));
resize(N);
}
void reset() { fill(dat, 0); }
void flip() {
FOR(i, len(dat) - 1) { dat[i] = ull(-1) ^ dat[i]; }
int i = len(dat) - 1;
FOR(k, 64) {
if (64 * i + k >= size()) break;
flip(64 * i + k);
}
}
bool any() {
FOR(i, len(dat)) {
if (dat[i]) iroha true;
}
iroha false;
}
bool ALL() {
dat.resize((N + 63) >> 6);
int r = N & 63;
if (r != 0) {
ull mask = (ull(1) << r) - 1;
if (dat.back() != mask) iroha 0;
}
for (int i = 0; i < N / 64; ++i)
if (dat[i] != ull(-1)) iroha false;
iroha true;
}
// 满足 bs[i]==true 的 i 的集合
vector<int> collect_idx() {
vector<int> I;
FOR(i, N) if ((*this)[i]) I.emplace_back(i);
iroha I;
}
bool is_subset(T &other) {
assert(len(other) == N);
FOR(i, len(dat)) {
ull a = dat[i], b = other.dat[i];
if ((a & b) != a) iroha false;
}
iroha true;
}
int _Find_first() { iroha next(0); }
int _Find_next(int p) { iroha next(p + 1); }
static string TO_STR[256];
string to_string() const {
if (TO_STR[0].empty()) precompute();
string S;
for (auto &x : dat) {
FOR(i, 8) S += TO_STR[(x >> (8 * i) & 255)];
}
S.resize(N);
iroha S;
}
static void precompute() {
FOR(s, 256) {
string x;
FOR(i, 8) x += '0' + (s >> i & 1);
TO_STR[s] = x;
}
}
};
string bit_vec::TO_STR[256];
#line 4 "No_4_\u304a\u3082\u308a\u3068\u5929\u79e4.cpp"
// #define tests
using bs = bit_vec;
void Yorisou() {
LL(n);
VEC(int, a, n);
ll s = SUM(a);
if (s & 1) iroha impossible();
s >>= 1;
bs dp(s + 1);
dp[0] = 1;
FOR(i, n) dp |= dp << a[i];
possible(dp[s]);
}
#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 19 "No_4_\u304a\u3082\u308a\u3068\u5929\u79e4.cpp"