/*
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣄⠉⠻⢿⣋⣥⣴⣶⣿⣿⣿⡿⠿⠿⠿⠿⠿⠿⠿⢶⣶⣤⣀⠙⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⣿⣦⠬⠉⠛⠉⠉⠀⠀⠀⠀⠀⠀⠀⣀⣠⣴⣦⣤⣄⣉⡛⠷⣮⣟⡁⠈⠉⠻⢯⣟⡻⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠿⠛⠛⠛⣛⡻⠟⠋⢁⣠⣤⠾⠛⠁⠀⢀⡤⢆⣠⣴⣾⣿⠿⠿⠛⠛⢛⡟⣻⣻⡙⢿⣟⠿⡿⣿⣦⣄⣈⠻⣷⡷⣮⣙⠿⣿⣿⣿⠟⠋⠉⠁⠀⠀⣠⣴⡶⣿⣿⣿⢿⡿⣿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣣⣶⣶⣶⡦⠚⠉⣀⣴⣾⠟⠋⠀⠀⠀⣠⠶⠋⢰⣯⡾⠛⣉⡠⠄⠒⢀⣬⠷⣋⢥⡑⢎⠲⡹⣯⡱⣍⠻⣿⣿⣿⣮⡹⣯⡟⣷⣌⠙⢿⣦⠀⠢⡠⣔⠛⢉⣥⣿⣛⡷⣹⣮⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣜⣯⠞⠁⣀⣴⣾⠿⠋⠀⠀⠀⠀⣠⠞⠁⢀⣴⠟⣁⡒⠍⢀⢠⣄⣶⠛⡑⣊⠔⢢⡙⢬⡓⢥⠻⣷⡌⡗⢦⡹⢿⣞⣷⢩⡟⣼⣛⣷⡄⠙⢷⣀⠐⣠⣶⠿⣛⡶⣫⣾⣿⣿⣿⣿⣿⣿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣇⡿⠁⣠⣞⣿⠟⡁⠀⠀⠀⠀⣠⠀⠉⠃⣠⠞⡥⠒⠄⢈⣤⢾⣻⠟⢁⠜⡰⠉⡜⠠⠖⣂⠹⠆⡍⣿⡎⡝⣣⡕⣫⢻⡞⡧⡞⡩⢿⡎⣿⣆⠀⠹⣾⠋⢱⡿⣏⣿⣿⣿⣿⣿⣻⣿⣿⣿⣻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⢁⣴⣿⠟⣡⠎⠀⠀⠀⢀⡞⠁⠤⢀⡼⠋⠀⠀⣠⠾⠛⢡⡾⢁⠰⡈⢆⢡⢃⠬⣉⠜⣄⠣⣩⠐⣿⡗⡘⣆⠹⣼⡱⣿⡡⢇⡛⣼⢿⡜⣿⣆⠀⠘⣿⣿⣻⣿⣿⣿⢿⣳⣯⣿⣿⡿⣯⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⣾⠟⢁⡴⠁⠀⠀⠀⣰⠏⠀⠀⣠⠟⠀⠀⣰⠞⠁⠀⣴⠟⠀⠄⢂⠑⣂⢆⢒⡐⣒⢊⣷⣐⣴⠡⢫⣷⠑⡬⢑⡸⡇⢹⣷⠱⠞⠁⠀⣷⢹⣿⡄⣧⡘⣿⣿⡿⣯⣟⣯⣿⡾⣿⢯⣿⢳⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⣃⣴⡟⠀⠀⠀⢀⡾⠁⡈⠀⣰⠏⠀⣠⠞⠁⡀⢀⣾⠋⠀⠀⡈⣧⠔⢀⠊⡤⠘⡬⣸⡿⡟⠁⠀⣿⡿⡀⠳⠀⢸⣧⠸⣿⡇⢠⢂⠳⡸⣎⣿⡇⣽⣷⡘⣿⣿⣿⣿⣿⣷⣻⡟⣿⢳⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢏⣲⣿⠟⠀⠀⢠⢣⣟⠃⡸⠀⣰⠏⢀⡾⠉⠀⠜⢃⡾⠁⠂⠀⣼⣿⠇⣀⠂⡜⠠⣯⢁⣿⠓⠁⠀⢸⣿⣷⡕⡨⣡⠂⣽⣦⢹⣷⡏⢬⡓⣥⢋⣽⣿⢼⣿⣿⢹⣿⣿⣿⣿⣿⣿⣿⣷⣿⡻⢿⣿⠻⠿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⣿⡿⠃⣼⣿⡟⠀⠀⠀⢢⠟⡜⢰⠃⣰⠏⣠⠟⠁⣀⠚⢀⡿⠁⡐⢀⡿⣿⠃⡐⣀⠣⡐⢣⠗⣾⡏⠤⣴⠀⣾⡿⣟⣧⡑⣡⠚⠤⡟⣾⡇⣏⢆⡓⡆⡧⢺⣿⣾⣯⣷⢛⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣾⣽⢷⣄⠈⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⢋⣵⣿⣿⣿⠃⣾⣿⢻⠀⠀⠀⢠⡟⢰⠇⡟⢠⡟⣰⠯⠀⠆⠠⢀⣿⠁⣰⠁⣼⣿⠟⣀⠒⠄⡡⠰⣍⣿⡟⢌⠒⡤⣹⡿⠁⣿⢿⡀⠧⡜⢒⡯⢼⡗⣽⢨⠼⡑⣎⢳⣿⣽⡷⣿⢢⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣷⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⣴⣿⣿⣿⣿⠇⣼⣿⠃⡏⠀⠀⢀⡾⢀⡞⢰⠃⣾⣳⣿⠁⡘⢀⣡⣿⠇⣰⠇⣸⢻⡏⠠⠰⡁⠌⢡⢃⣾⣿⡁⢮⢂⣾⡿⠁⠀⢹⡞⡏⡞⡸⠤⣟⢾⡏⣿⢠⢻⡱⣌⣻⣿⢼⡿⣽⣚⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃⠀⠻⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⢰⡿⠃⣰⠃⠀⠀⣸⠇⣾⡇⢾⣹⢷⣿⠇⠀⣤⡾⢋⣿⡾⠃⣼⢏⣿⠁⣊⠔⠡⣼⠗⣦⣿⠃⢼⣲⣿⠏⠀⠀⠀⠀⣿⣕⡱⣃⢣⡿⣿⢃⣿⢌⡳⣚⡾⣼⣿⢻⡿⣽⣣⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣀⠀⠀⠈⢻⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡷⠟⠃⣼⣿⡀⠀⢀⡿⢰⢻⠀⣿⣿⣟⡟⣠⠞⣋⣠⣼⠏⢡⣼⡟⣼⢃⠰⠤⣈⡿⢋⣼⣿⡏⢌⣴⣿⠥⡤⣤⣤⣀⣀⣸⡇⠳⣇⢮⣿⡿⢌⡟⡬⢇⣿⢷⣿⣏⣿⡽⣾⢵⣿⣿⣿⣿⣿⣿⠿⠿⠿⠛⠛⠛⣇⠘⣶⣄⠀⠀⠙⢿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠃⠂⣼⠿⣿⡇⠀⣸⠃⣏⣾⢸⣿⣿⣿⣷⠟⠛⢋⣿⣁⣶⠛⢹⢇⡟⠠⠌⣰⣿⣵⠿⢫⡏⣴⡾⠋⠀⠀⠀⠀⠀⠀⠈⠉⢿⡱⠸⣼⣿⡏⣼⡧⢹⢮⣟⣾⣿⣘⣿⡽⣳⣾⣿⠿⣟⣯⠉⠀⠀⠠⣤⣀⠀⢀⣾⡄⢰⡈⠳⣄⠀⠈⢻⡝⢿⣿
⣿⣳⣿⣻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠁⡾⣼⡿⣸⡏⡇⠀⡿⠀⡏⣿⢸⣿⣿⡟⠁⢀⣴⡿⠛⠉⠀⠀⡞⢸⠇⣐⣾⣿⠟⠁⣰⣿⠿⠋⢀⣀⣀⣀⣀⠀⠀⠀⠀⠀⠈⣷⣣⣿⣿⢡⣿⡘⢧⣿⢣⣿⢣⣾⣯⣿⡟⠉⣠⣶⣿⡟⠀⠀⠀⠀⠀⠈⢻⣿⣿⣷⠀⢇⠀⠈⠳⠀⠀⠙⣆⠉
⣿⣽⣻⣟⡿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠟⠀⣸⣽⢿⣇⡿⡇⢡⠀⡧⠀⣧⣿⢸⣿⡿⠀⢶⣏⡀⠀⠠⠤⡀⠀⡏⢾⣡⡾⠛⠀⣠⠾⠛⠁⠀⢀⣠⣧⣿⣿⣾⣶⣷⣟⣀⠀⣀⣸⣿⣿⡟⣸⢧⢹⢯⣭⣿⢝⣾⡿⣯⣿⣿⣾⣿⣿⣯⣤⣤⣤⣤⣀⡀⠐⠺⠿⣿⣿⡆⢸⡄⠰⠄⠈⠂⠀⠈⢷
⣿⣿⣿⣿⣿⣿⣾⣯⣿⣟⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣿⣻⣽⣿⠏⠀⣰⢿⠇⣾⢸⣷⣧⢸⣤⣇⠀⣿⣿⣸⣿⣿⣶⣿⣿⣿⣿⣿⣶⣄⡀⡇⣹⡟⠁⠀⠊⠁⠀⠀⢀⣴⣿⠟⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⣄⣹⡟⢠⡟⣦⢿⣙⣾⣷⣿⣿⣿⠿⡿⣟⠛⣿⠛⠛⢿⣿⣿⣿⣿⣿⠗⠀⠀⠀⣿⣷⠘⡇⢈⠡⢂⠀⠀⠀⠀
⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠿⠿⣞⢻⣏⢿⡶⣽⣾⢿⣾⣯⣷⣿⣿⣿⣿⣿⠏⠀⣰⣿⡟⢈⡟⢸⣿⣿⠀⢿⣿⠀⣿⣿⣇⣿⣿⡿⠛⢁⣾⠟⣿⢿⣿⣷⣿⡟⠀⠀⠀⠀⠀⠀⠀⠚⠋⠀⢸⣿⣤⣿⢏⣿⡿⣿⢙⣿⣿⢿⡿⠁⡼⢸⢇⣿⣾⣿⣷⣿⣶⣿⣿⣿⣦⣧⣽⡅⠄⣼⣿⣿⣿⠟⠁⠀⠀⠀⠛⠉⠛⣷⡇⢐⢂⠐⡈⠤⠀⠀
⣄⣉⠛⡋⠏⢭⡉⢖⡁⢎⣍⣳⣬⣳⣾⣯⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡏⠀⣰⣿⠙⢀⣻⠇⣼⣿⢻⡆⠘⣿⡆⢿⡭⢿⣿⣿⣇⠀⠘⣿⡞⣿⣾⡟⣿⠽⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⣿⠋⠻⣷⠟⢀⡽⣸⠏⢁⡟⠀⣠⣽⣿⣿⣿⣿⣟⣿⣿⣿⣿⣿⣿⣁⣴⡿⢰⢛⣿⣿⡛⠀⠀⠀⠀⠀⠀⠀⣀⣠⡟⣷⣆⠦⠁⠒⠨⠀⠂
⠉⠛⠛⠛⠿⠳⠟⠻⠛⠟⠛⠛⠻⠿⠿⢿⣿⡿⠿⠛⠛⠉⢉⠛⠻⠿⣿⠁⢰⣿⡏⡄⡬⣿⠀⣿⣿⡹⣽⡄⠙⣿⣾⡿⡽⣯⣇⠹⣦⠀⢿⣄⠈⢻⣷⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⢧⣤⣬⣤⡾⠝⠁⢠⣾⠶⠛⢯⣻⣟⣣⣶⣿⣿⣯⡛⠛⣿⣧⣸⣿⣿⣧⣸⢿⣿⣿⣿⠶⣤⣤⣤⣶⣾⣿⣿⣿⡇⣿⡿⣷⣯⣀⡁⠀⠀
⠀⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠀⠠⠀⠀⢀⣤⠔⠊⠁⠀⢀⣴⡇⢀⣿⣿⢃⢡⢹⣿⠀⢹⣿⢵⢫⡿⣄⠘⢷⣿⣵⣿⣿⠀⠊⠓⠖⠋⠙⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠰⣺⠏⠀⢀⣾⣷⡿⣿⣿⣿⣿⣿⣿⣿⣧⡉⢻⣿⣿⣿⣿⣿⡀⠀⣀⣠⣼⣿⣿⣿⣿⣿⣿⣿⣿⢧⣿⡿⣽⣿⣷⣦⡄⠀
⡐⠦⡄⡤⡄⣀⡀⢀⡀⣀⣀⣀⣁⣀⣤⣴⠶⠛⠉⠀⢀⣀⣴⡾⣟⣿⡇⢸⠿⣿⠀⢸⡆⢿⠀⢸⣿⡿⢋⡔⣩⣷⣌⠻⢿⣿⣿⡗⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡼⠁⣠⣶⣿⣿⣻⠿⠛⠉⠉⠛⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣿⣿⣼⣿⣿⡷⣯⢿⣿⣿⣦
⣭⣷⣵⣶⣵⣦⣍⣲⣘⣴⡶⠴⠚⠋⠉⠀⢀⣠⣴⣾⣟⣿⡷⠟⠛⢹⡇⣼⣿⡟⠀⢸⡇⢾⡆⠀⣯⢐⣣⣾⣿⣿⣿⣷⣮⣽⣿⣇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⣯⠴⢚⣿⠞⣩⠞⢁⣀⣤⣤⣤⣤⣤⣽⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⣽⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣽⣻⢿⣯⣿
⠉⠉⠉⠉⠉⠁⠁⣀⣀⣀⣤⣤⠶⠶⠾⠿⠛⠛⠋⠉⠁⠀⣀⣤⣶⣿⡇⢼⣿⡇⠀⣽⡀⣿⢷⠀⢹⣾⣵⣿⣿⣿⣿⣿⣿⣿⣿⣿⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠊⠉⠁⠀⢀⣾⢃⣾⣿⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣳⢿⣻⣿⣿
⣁⠉⠀⠈⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣠⣤⣴⣶⡿⣟⡹⢦⣫⣿⡸⣿⡇⠀⡿⣱⡏⣜⣧⡀⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⣾⣿⣿⣿⣿⡿⠟⠛⠛⠛⠛⠛⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠿⢿⣿⣟⡿⣽⣯⣿
⠍⠛⠓⠲⠒⠲⠖⠶⠶⠶⠶⠶⠿⣟⣿⣿⣻⢟⡽⢯⣓⣳⠹⣭⣷⣿⡟⣷⣽⡇⠀⣧⣿⣿⣿⣻⣿⣮⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⣿⣿⣿⣿⣿⣿⣿⣿⣶⣦⣄⢀⡤⠞⠉⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣡⢿⣹⢾⣿⣿⣻⣟⣾⢿
⣀⣩⠤⠓⠚⡉⢑⠌⠒⢁⣩⣴⣿⣿⡻⢶⣫⢏⡵⣓⢮⣼⣿⢻⡾⣏⣾⠟⣹⡇⠀⣿⣿⣟⣳⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠲⢤⣴⣾⣻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣄⠀⠀⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣽⣾⡿⣿⣿⣿⣯⢿⡾⣿
⠀⠠⠠⠐⠃⢀⣠⣴⣾⡿⠿⣛⣯⠷⣛⣜⠶⣩⣶⣽⣿⢻⣼⣟⢳⣾⣵⣿⣿⣷⠀⢻⣿⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣰⠿⠛⠉⠀⠀⠀⠀⠈⠙⠻⢿⣿⣿⣿⣿⣇⠀⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⣿⣻⣽
⣠⠤⠴⠒⠛⠉⢉⣠⣤⡶⣟⢻⣬⢳⢣⣮⣷⣿⢟⣳⣾⣟⣳⣾⣿⣿⣿⣿⣿⡿⣧⠈⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣤⠶⡾⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣿⣿⣿⣿⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣟⣯⣿⣿⣿⣿⣿⡷⣯⣟⣾
⣀⣀⠤⡴⡲⢞⣏⣳⢥⠻⣜⣣⣶⡻⣟⡻⣽⣼⣿⣛⣾⣾⣿⣿⣿⣿⣿⡿⣏⣳⣿⣦⣹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣀⠀⠀⣀⣀⡴⠶⠛⠉⣀⡾⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⣟⣿⣿⣿⣿⡿⣽⢯⣿
⡝⣮⢳⢳⡝⣎⠾⡴⢯⡟⣿⣹⣶⣽⣾⡿⣟⣳⣷⣿⣿⣿⣿⣿⣿⡟⣧⣻⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣶⣶⣦⣴⡟⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡗⣯⢿⣾
⣽⣲⣏⣷⣹⡮⢟⡹⢛⢫⣍⣥⣾⣟⣷⡟⠋⠁⢸⡿⣯⣹⣿⣿⣮⣽⣿⢿⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⡿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⡿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣟⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⣿⣻⣞
⣿⣿⣿⣿⣿⣿⢷⣾⣳⢿⡿⢿⣛⠩⠄⢷⣀⣠⡿⢁⡤⠠⠄⠀⢀⣠⣴⣾⣿⡿⢿⢿⠻⢟⠿⣿⣻⣟⣾⣟⣿⣷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣟⣿⣽⣯⣥⣥⣉⣙⣿⣿⣿⣿⣿⡿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠀⠀⠀⣠⣾⣿⣿⣽⣯⣿⡿⣿⢯⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⢇⣯⢷⣻
⣿⢿⣻⡽⣧⣻⣯⣶⡟⣿⣹⠷⣎⡟⣭⢢⡍⢭⡐⣌⡒⠉⣠⣴⣿⣿⣿⣿⣿⣿⢢⢍⠺⢭⣚⣯⣷⢯⣿⢾⣟⣾⣿⣿⣽⣿⣿⢿⣿⡿⣿⢯⡿⣽⢿⣻⢿⣿⢿⣟⣯⣿⣿⡿⠟⢹⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠛⠻⢿⣿⣿⣻⢷⣿⣷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⣷⣿⣿⣿⣿⣿⣿⣿⣿⢸⢮⡿⣼
⣿⣿⣷⣿⣿⣏⡘⢷⣿⣳⣯⣟⣽⣺⣵⣳⣮⠷⢚⣠⠶⣟⡿⣻⣟⣿⣿⣿⣿⣻⣇⢎⣏⢲⡿⣱⣿⣻⣽⣟⣿⣿⣻⣽⣿⢯⣿⡿⣯⡿⣯⢿⣹⣏⢿⣹⣟⣾⣿⣽⠟⠛⠉⠀⠀⢘⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠁⡀⠀⠈⢿⡸⣿⣷⣿⣿⣿⣿⢿⡿⣿⣻⣿⣽⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡏⣼⢧⣻⢟
⣿⣿⣟⣿⣯⣷⣹⠷⣮⣟⠛⠛⠛⠋⠉⣉⣠⣴⣿⣾⣿⣿⣷⣷⣟⡿⣫⣿⣿⣽⣿⡞⣨⡟⣼⣟⣷⣻⢷⣻⢿⡽⣯⣿⣾⢿⣯⣟⣷⢻⣭⣛⡶⣹⣿⣭⣉⣍⣁⣤⣤⣤⣲⣶⣶⣿⣿⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠐⣿⢦⣀⣾⠃⣼⣿⢿⣿⣿⣿⡟⢿⣟⣿⣿⡿⣿⣿⣿⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢣⢟⡶⣫⢏
⣿⣟⣿⣻⣽⣟⣿⢿⣻⣟⣻⣿⣿⣲⣷⣿⣿⣿⣿⣿⡿⣿⣿⣿⣿⣿⣟⡼⢿⣷⣻⣿⣷⣹⣟⣾⣳⢯⡿⣽⢯⣟⣷⡿⣽⣟⡾⠿⠚⠛⠋⠋⠙⠉⠉⠁⠀⠀⠀⠀⢨⣿⣿⣿⣿⣿⣿⣿⣷⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢧⡻⣟⣦⢉⢷⣾⣿⣿⣿⣿⣿⣿⣾⣽⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣇⠾⣭⢞⡱⢮
⡟⡻⢟⡿⣯⣿⢾⡿⣿⣿⣿⣾⣿⣿⣿⣿⡿⣯⣟⣾⣟⡿⣞⡿⣿⣿⣿⡭⠽⡻⣷⣟⣿⣧⣛⡾⣭⡟⣽⣞⣻⢼⣯⣿⠟⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣰⣿⣿⣿⢻⣿⣿⣿⣿⣿⣿⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡀⢀⣽⣯⣽⣤⡚⣿⣿⣿⣿⣿⣿⣿⣿⣿⡻⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⢋⣵⠻⡜⣮⣝⣻
⡜⡥⢋⣞⡹⠊⢻⡝⣿⣞⣿⣻⣿⣿⢿⡧⣟⣷⣛⢾⣹⢻⡽⣻⣗⣿⣿⣿⣷⡷⣷⢿⣿⣿⣿⣿⣿⣿⣱⣻⢮⢷⡿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣶⣶⣿⢯⣼⡟⣱⣶⣿⡿⠻⣿⣳⡿⠃⠙⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣾⣿⣿⣿⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣿⣿⣿⣿⣿⣿⡿⠟⠋⣁⣶⢿⢣⡻⣜⠾⣼⣻
⡦⣑⣡⢂⠱⢐⠣⡜⣥⡛⣾⣱⣿⣿⣿⡜⢧⡣⠽⠦⠙⠦⢓⡳⠾⣴⢭⣻⣷⣿⢾⣛⣯⣿⡿⣹⢾⣿⠳⣽⣺⡟⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢨⣿⣿⣿⣿⠿⠛⠋⠁⠀⠀⢻⡿⠁⠀⢠⣿⣿⣦⡀⠀⠀⠀⠀⠀⠀⠀⣠⣿⣿⣿⣿⣿⢘⡻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣛⠉⠀⢄⣳⡟⣏⢮⢣⡷⣭⣟⢷⣹
⣷⢯⣟⣾⣻⣞⢦⣰⡅⢋⡐⢿⣿⣻⢷⡸⣋⠁⠀⠀⠈⠀⠀⡱⣉⠧⣺⡯⡜⣿⣿⡿⣟⣯⠷⣏⢾⣟⠷⣤⣿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣾⣷⡾⠛⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⣿⣿⣿⣦⡂⠀⠀⠀⢀⣼⣿⣿⣿⣿⣿⡇⢸⡇⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⢿⠋⢉⣠⣾⡟⢯⡜⣎⢮⢷⣹⠶⣯⢾⣽
⣿⢯⣟⣾⣳⢯⡿⣱⣟⢯⣿⣿⣿⣟⣳⣧⡇⠄⠀⠀⠀⠀⠀⠀⢂⣓⣿⡱⢭⣿⡿⣝⢯⡞⡽⣚⢬⠹⢷⣭⠏⠀⠀⡴⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠼⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⣿⣿⣿⣿⣿⣶⣶⣶⣿⣿⣿⣿⣿⣿⣿⡃⣼⡏⡜⣻⣿⣿⣿⣿⣿⣿⣿⡓⠦⡜⢢⣿⣶⡿⣏⡗⣞⣣⢾⡹⢯⣞⡷⣻⣭⣟⡾
⣟⡿⣞⣳⣽⢫⠾⣳⢯⣻⣿⣾⣿⣾⠏⠙⣿⣆⠀⡐⠀⠀⠀⡜⣤⣹⢧⢣⣿⡿⣝⡯⣞⡝⢶⠩⢆⣽⣾⡿⢀⡴⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣀⣤⣤⣶⠀⠀⠀⠀⠀⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠠⣿⣿⡜⡽⣿⣿⣿⣿⣿⣿⣿⣿⢒⡍⣳⣿⢻⡵⣋⡾⣼⣣⢿⣽⣻⢾⣽⣷⣻⢎⡿
⣯⢟⡽⠣⠌⣉⣾⣿⡿⣷⣿⣿⣶⣿⣄⣸⣿⣿⡷⣧⣶⣦⣻⣜⡦⣿⡙⣶⣿⣻⡝⣾⢱⡚⣥⣿⠟⠁⠘⣷⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⡤⠖⠒⠋⣉⣭⡽⣟⣫⣭⣿⣷⠀⠀⠀⠀⠀⠀⠉⠛⠻⢿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣘⣿⣿⣧⣛⣿⣿⣿⣿⣿⣏⢭⠣⣍⡒⣽⣯⢷⣻⡽⣽⣳⢯⣟⣾⣽⣿⣟⡷⣯⣻⣽
⡟⢎⣹⣵⣾⡿⣿⢷⣿⣿⣿⡿⣽⣻⣿⣟⡾⣝⣿⣿⣶⣿⡿⣭⣿⣳⢋⣾⣟⣷⡻⣜⣷⠟⠋⢀⣠⣴⣾⣏⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⠖⠋⠁⣀⣤⣶⡿⣿⠽⡾⣿⣿⡙⣞⡿⣧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠻⣿⣿⣿⣿⣿⣿⡗⣼⣿⣿⣷⡽⢾⣿⣿⣿⣿⡧⢚⠳⢰⣽⣿⡽⣯⡷⣿⡽⣯⣿⣾⣿⣿⣻⢾⣽⣳⣟⣾
⣭⣿⣿⢿⣽⣿⣦⣶⣽⢻⣯⣿⠷⠛⣩⣿⣯⠽⣿⣿⣟⡾⣽⢯⡟⡭⢿⣿⣻⣶⠿⢋⡴⣠⣶⡿⣿⣿⢿⣙⡻⣷⣦⠀⠀⠀⠀⠀⠀⣀⣤⡶⠛⣁⣴⢞⣫⣽⢟⡽⢫⣑⢛⣒⢳⣾⡯⣽⣾⣿⣧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⢌⠿⣿⣿⣿⣿⡟⣼⣿⣿⣿⣽⣻⣿⣿⣿⣿⣇⣣⣷⣿⣿⣟⡿⣽⣻⣷⣿⣿⣿⣿⣿⣳⣯⣟⣾⣳⣿⣿
⣿⣿⣯⣹⣿⢾⣿⣿⡿⠟⢋⣡⣾⣿⣿⣻⢿⣷⡝⣿⣿⣟⣭⣛⡯⠵⣿⣿⡽⣹⣾⣿⣿⡿⣿⡽⣿⣟⡷⣯⣟⣿⠉⠀⠀⠀⠀⣠⣾⡿⣋⣴⣾⡹⣦⡿⣫⢓⡞⢊⣕⣺⣹⡎⣿⣟⣿⣿⣾⣿⣿⣇⠀⠀⠀⠀⠀⠀⠀⡈⢆⠲⡜⢯⣿⣿⣿⡳⢼⣿⣿⣿⡾⣽⣿⣿⣿⣿⣿⣿⣿⡿⣽⣾⣿⣿⣿⣿⣿⣿⡿⣟⣾⡽⣾⣽⣾⡿⣟⣾
⣿⣿⣿⣿⣽⠿⠛⣩⣴⣾⣿⣿⡿⣷⣻⣽⣯⢿⣿⣌⢿⣿⣿⣟⣯⢻⣿⡿⣽⣿⡷⣿⣶⡿⣽⣻⣿⣿⣿⣿⣾⣿⣷⡀⠀⣠⣾⣿⡿⣼⢿⣛⣴⣿⡫⣵⣛⢏⡶⣏⣺⣭⢷⣻⢷⡞⣿⣷⣿⣿⣿⣿⡆⠀⠀⠀⠀⠀⠐⡂⢌⠲⣉⠖⡰⣿⣿⣱⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣟⡷⣿⢯⣷⣿⣿⣻⣽⣟⡿⣿
⡉⠉⠈⠉⠁⠘⠛⠛⠿⠿⣿⣷⣿⣽⣻⢾⣽⣻⢾⣿⣆⡻⣿⣿⡖⣿⣿⣽⣿⣟⣿⣷⣿⣟⣿⣽⣿⣿⣿⣿⣿⣿⣿⣷⣾⣿⣿⣿⣿⣯⢿⣾⡿⣧⣿⣭⢯⣟⣷⣩⣽⣳⣟⡿⣿⣻⣿⣾⣿⣿⣿⣿⣇⠀⠀⠀⠀⠈⠤⠑⠬⡱⣈⠎⡕⣿⣿⡎⢼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⣷⣻⢾⣽⣿⣿⢿⣽⣞⣿⣳⣿⡽⢫
⣿⢿⣶⣶⣤⣬⣤⣉⣐⠡⠒⠜⢪⠝⡹⠻⠾⠿⣧⣿⣿⣷⣹⣿⡿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣿⣿⣿⣿⣿⣷⣿⣿⣾⣽⣿⣷⣿⣻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡄⠀⢀⠄⠑⡨⢡⠓⣄⠣⠜⡁⣿⣿⡇⢺⣽⣿⣿⣿⣟⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣿⣿⣾⣿⣹⡟⢎⣵⣻
⣿⣿⣿⣾⡽⣷⣯⣿⣿⣿⣟⣾⡶⢦⣥⣭⣈⣃⠐⠢⠡⢨⠉⠻⣇⠀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠀⠠⠈⣀⠃⢆⠱⡀⢓⠨⡁⣿⣿⣧⠒⣼⣿⣿⣿⣿⡾⣽⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣾⣿
⢶⣿⣾⣽⣿⣿⣳⣿⣾⣽⣻⣟⢿⢿⢶⡾⣿⣽⣿⣛⣷⠶⡾⣦⣽⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡆⠠⢁⠂⡍⠠⠂⠌⠄⢢⡅⡿⣿⣿⡎⢶⣻⣿⣿⣿⣿⣧⣛⡞⡙⢿⣿⣿⢿⣨⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣟⣿⣿⢯⣿⡟⣽⣿⡿⣿⣿⣿⣮⢷⣽⣶⣧⢿⡬⣛⣵⢒⢦⢲⣽⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⠐⢡⠂⠌⡠⠡⠈⣀⣶⣧⠀⢿⣿⣧⢓⣾⣿⣿⣿⣿⣿⣿⣾⣅⠀⠈⠙⢿⣯⣷⣻⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⠛⠻⠿⢿⣻⣟⡿⣙⣾⡿⣽⣳⢟⣼⣿⡓⣾⢟⣻⡷⠾⣷⣎⡝⢦⠣⡼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⠁⡈⢂⠈⠐⢀⢰⣶⣿⣿⣿⡄⢸⣿⣿⣮⢾⣿⣿⣿⣿⣿⣿⣿⣿⣷⣦⡀⠀⠈⠛⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣴⣤⣆⣤⣥⢿⣳⣻⡿⣝⡯⢷⡟⣞⣿⢱⣿⢎⡼⢃⡟⠴⡯⢱⠎⡕⡒⢼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣇⣴⣶⣿⣶⣧⣶⣿⣿⣿⣿⣿⡇⠀⣿⣿⣿⣿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⡀⠀⠈⠛⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣏⣾⡿⣟⡯⠫⠏⠉⠙⠛⠿⠷⢿⣼⡃⣿⢏⣏⢏⡳⣜⣣⣝⣦⡷⣌⠱⣸⣧⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢻⣿⣿⣿⣿⣿⣇⣼⡿⣿⣿⣿⣻⡼⣻⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣄⠀⠀⠈⠙⠿⣿⣿⣿⣿⣿⣟⣿⣿
⣿⣻⡽⣯⢧⡟⣿⡶⠖⠲⣤⣤⡾⢧⣓⡯⢺⣌⡛⢶⣉⣡⣉⠉⠓⠌⣡⡟⣸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣽⣿⡿⣯⣽⡿⣿⣿⣷⣿⣵⢫⡞⡽⣻⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣶⣄⡀⠀⠈⠛⢿⡿⣿⣿⣿⣿
⢿⣳⢿⣼⠣⣛⠶⣭⣛⢿⡻⣍⢏⠧⡼⡸⢅⡎⡙⠦⢭⠩⢍⣟⢛⣲⡟⠀⣿⣿⣿⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣽⣾⢻⡜⡽⣿⣿⣿⣿⣿⣾⣵⣣⢏⣴⣨⢍⠩⣉⣉⣉⢉⠉⠉⡉⠓⢲⡀⠀⠀⠙⢷⣮⣍⡛
*/

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#include "richest.h"
using namespace std;
#define sz(x) (int) (x).size()
#define i64 int64_t
#define all(x) (x).begin(), (x).end()

vector<int> a,b,c;

int subtask_1(int N) {
    a.resize(0);
    b.resize(0);
    for (int i=0; i<N; i++) {
        for (int j=i+1; j<N; j++) {
            a.push_back(i);
            b.push_back(j);
        }
    }
    assert(sz(a)<=499500);
    c = ask(a,b);
    set<int> ok;
    for (int i=0; i<N; i++) {
        ok.insert(i);
    }
    for (int i=0; i<sz(c); i++) {
        if (a[i]==c[i]) {
            if (ok.count(b[i])) ok.erase(b[i]);
        } else {
            if (ok.count(a[i])) ok.erase(a[i]);
        }
    }
    assert(sz(ok)==1);
    return *(ok.begin());
}

const int mxn=1e6+5;

vector<int> ops = {2,2,2,2,3,6,19,1000000};
int good[mxn];
vector<int> cv,pv;

int subtask_2(int N) {
    memset(good,0x3f,sizeof(good));
    cv.clear(); pv.clear();
    for (int i=0; i<N; i++) {
        cv.push_back(i);
    }
    for (int DIV : ops) {
        vector<int> cbk;
        a.clear();
        b.clear();
        vector<vector<int>> cbks;
        for (int i=0; i<sz(cv); i+=DIV) {
        	if (i+DIV >= sz(cv)) break;
        	cbks.push_back({});
        	for (int j=0; j<i+DIV; j++) {
        		cbks[sz(cbks)-1].push_back(cv[j]);
        	}
        }
        
        if (DIV==3) {
        	cbks[0].push_back(cv[sz(cv)-1]);
        }
        if (DIV==6) {
        	cbks[0].push_back(cv[sz(cv)-1]);
        }
        if (DIV==19) {
        	cbks.push_back({});
        	for (int j=sz(cv)-1; j%DIV!=18; j--) {
        		cbks[sz(cbks)-1].push_back(cv[j]);
        	}
        	for (int j=0; j<5; j++) {
        		cbks[sz(cbks)-1].push_back(cbks[j][18]);
        		cbks[j].pop_back();
        	}
        }
        for (auto cbk : cbks) {
        	for (int i1=0; i1<sz(cbk); i1++) {
                for (int i2=i1+1; i2<sz(cbk); i2++) {
                    a.push_back(cbk[i1]);
                    b.push_back(cbk[i2]);
                }
            }
        }
        
        c = ask(a,b);
        for (int i=0; i<sz(c); i++) {
            if (a[i] == c[i]) {
                good[b[i]]=0;
            } else {
                good[a[i]]=0;
            }
        }
        swap(cv,pv);
        cv.clear();
        for (int i : pv) {
            if (good[i]) cv.push_back(i);
        }
        if (sz(cv)==1) {
            return cv[0];
        }
    }
}

int richest(int N, int T=1, int S=1) {
    if (T==1) return subtask_1(N);
    assert(N==1000000);
    return subtask_2(N);
}