// _
// ^ ^ //
// >(O_O)<___//
// \ __ __ \
// \\ \\ \\\\
/*
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣿⠷⢛⠩⣡⠦⢂⢂⢂⠂⡂⢂⢐⢀⠂⠄⡂⠄⢂⢐⠠⢀⢂⢐⢀⢂⠄⡂⡂⡂⠢⠡⡂⠪⡐⢅⠪⣙⢛⡻⡻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣯⣿⣯⣿⣯⣿⣯⣿⣽⣿⣺⡫⣿⣽⣯⣿⣽⣯⣿⣽⣯⣿⣽⣯⣿⣽⣯⣿⣽⣯⣿⣽⢾⣻⣵⢞⣴⠟⡡⡊⠄⠢⢐⠨⢐⢐⢐⠠⢁⠅⡂⠌⠔⡐⡨⢐⠐⡐⡈⡢⢑⢐⢅⠪⡘⢔⠌⡪⢐⢅⠇⡎⡪⡪⣚⢮⡻⡾⣿⣾⣿⣽⣯⣿⣾⣿⣾⣿⣽⣿⣽⣯⣿⣽⣯⣿⣽⣯⣿⣽
⣿⣻⣿⣽⣿⣽⣿⣻⣿⣽⣞⢽⢽⣿⣟⣿⣿⣻⣿⣟⣿⣿⣻⣿⣟⣿⣟⣿⣻⣯⣯⣷⣿⣻⣚⣞⠵⡩⢂⠊⠌⠨⡐⠨⢂⢂⠢⠨⡐⢔⠨⡘⢌⢐⢐⠔⡡⢂⠢⠪⡨⡢⢱⠨⡊⢆⢣⢪⠢⢅⠣⡣⡣⡱⡑⡕⡯⣿⣾⢿⣾⣿⣻⣿⣯⣿⣾⣿⣯⣿⣟⣿⣟⣿⣿⣻⣿⣟⣿⣟
⣿⣿⣟⣿⣽⣿⣻⣿⣻⣿⣻⣿⣻⣯⣿⣿⣽⣿⣯⣿⣿⣽⣿⣯⣿⣿⣻⣿⢿⣻⣿⣻⣿⢻⡝⡪⡑⢌⢐⠁⠌⡂⡊⢌⢂⢂⠅⢕⠨⡂⢕⠨⡢⡑⢔⢑⢌⠆⢕⢑⢌⢪⢊⢎⢎⢎⢪⡸⡸⡱⡱⡌⡎⣞⢼⢸⢪⢮⡻⣿⣿⣾⣿⣯⣿⣿⣽⣷⣿⣟⣿⣟⣿⣿⣽⣿⣯⣿⡿⣟
⣿⣯⣿⣿⣟⣿⣟⣿⣟⣿⣟⣿⣟⡯⣿⣯⣿⣯⣿⣯⣿⣯⣿⣯⣿⣟⣿⡿⣿⡿⣟⣯⡾⢣⢑⠌⡐⡐⡐⡐⠅⡂⡪⠐⡐⠔⡅⢕⠨⢌⢢⠣⡢⡱⢡⢃⢎⠜⡨⡊⡆⢎⢪⡪⡎⣞⡜⡼⣸⠸⣜⢼⢸⢬⢳⢳⡱⡱⢕⢇⠯⣷⣿⣯⣷⣿⣟⣯⣿⣿⣻⣿⣿⣽⣿⣽⣿⣽⣿⣿
⣿⣿⣽⣾⣿⣟⣿⣿⣻⣿⣟⣿⣷⢿⣟⣿⣽⣿⣯⣿⣯⣿⣯⣿⣯⣿⣻⡿⣟⣟⣯⠷⢩⢂⢂⢊⢐⢐⠰⡈⡂⡪⠠⡑⡌⠕⡌⡢⢣⢑⢅⢇⢪⠸⡰⡱⡘⡌⡆⡣⣪⢪⢪⡪⡎⣗⢵⢝⡮⣣⡣⡫⡺⣜⢵⡓⡽⡸⡸⡱⡹⡘⢾⣽⡿⣯⣿⣿⣟⣿⣟⣿⣾⣿⣯⣿⣿⣽⣿⣷
⣿⣾⡿⣟⣷⣳⣻⣿⣻⣯⣿⣿⣻⣿⣿⢿⣟⣯⢯⢯⣿⣿⣽⣿⣻⣿⣻⣿⣿⢿⢫⢘⠔⢐⢐⢐⢐⠔⠡⢂⢒⢌⠪⡢⡑⡅⢇⢊⢆⢣⢱⢸⠸⡘⡌⣆⢳⢨⢪⢪⢪⡪⣣⢫⢞⢜⢕⢗⢝⢮⢺⡸⡜⢎⢮⢺⢜⢜⢜⢜⢜⢌⢇⢟⣿⣿⣟⣷⣿⡿⣟⣿⣿⣾⢿⣻⣾⣿⣷⣿
⣾⡿⣿⣿⣿⢿⣽⣿⣟⣿⣿⣽⣿⣽⣾⣿⣿⣿⣽⣽⣿⣽⣿⣽⣿⣟⣿⣯⠟⢕⢡⢑⠨⢐⢐⢐⠔⠡⢁⠢⡱⢰⢑⠱⡐⡕⢅⢕⢱⢱⢱⢱⠱⡱⡱⡱⡕⡕⡵⡹⣜⢸⢸⢸⢱⢕⢕⢕⢭⢳⡱⡕⣝⢜⢜⡜⡎⣎⢎⢎⢜⠜⣜⢜⢷⣿⣻⢿⣻⣿⣿⣿⣾⣿⣿⣿⡿⣿⣾⣿
⣾⣿⣿⢿⣾⣿⣿⡽⣿⣻⣽⣿⣾⣿⢿⣻⣽⣾⣻⣿⣽⣿⣯⣿⣯⣿⠽⡂⡣⢑⠐⢄⠕⠡⡐⢌⠌⢌⠢⡱⠸⡐⡅⡣⡱⡸⡐⡕⡱⡑⡅⡇⡇⡣⡣⡫⡣⣪⡎⡇⣇⢣⢱⢱⢱⢱⢑⢕⢕⢕⢕⢕⢕⢕⢕⢜⢎⢮⢢⢣⠱⡑⡜⡵⡱⡻⣿⣿⡿⣿⣾⣿⣾⣿⣾⡿⣿⣟⣿⣾
⣻⣯⣿⣿⢿⣻⣽⣿⢿⣿⢿⣻⣗⢯⡻⡻⡿⣿⣿⣻⣯⣷⣿⡷⣟⣍⣪⢴⡜⡐⢌⠢⠨⡨⠨⡐⢌⠆⡕⢜⠡⡱⠨⡢⡣⣊⢢⢱⠱⡱⡱⡱⡡⡣⡣⡣⡱⣯⢿⡜⡔⡕⡅⡇⡇⡕⡕⢕⢅⢣⢣⢣⢣⢣⢣⠣⡣⡣⡣⡣⡩⡊⢆⡻⣽⡜⣽⣷⣿⣿⣷⣿⣷⣿⣷⣿⣿⡿⣟⣿
⢯⣞⣮⣻⡻⣿⣿⢿⣿⢿⣿⣿⢗⢧⡫⡮⣻⣿⣽⣿⡿⣟⣿⣿⣻⣽⡛⢕⣨⡬⢂⢐⢑⠠⠡⡘⢔⠱⡘⠔⡑⢜⢨⠪⡒⡔⡸⡰⡱⡱⡑⡕⡌⡎⡜⡰⡽⣯⢷⢯⡪⡪⡸⡨⡪⡸⡸⡸⡸⡘⡜⡌⡎⡜⡔⡕⢕⢕⢕⠕⡌⠌⡆⢇⡻⣟⣎⢷⣿⣷⣿⣷⣿⣯⣿⣯⣷⣿⣿⣿
⢕⣗⣵⣳⢽⣟⣿⣿⡿⣿⣿⣽⣏⢗⣝⢮⣳⣿⡿⣷⣿⣿⣿⣻⣯⢗⣮⡏⡃⡂⡂⠔⡡⠈⡔⢌⠢⡑⠅⢅⠕⠅⡢⡣⠣⡊⢔⠕⡜⢜⢜⠜⡌⡎⡊⣞⣯⡯⡿⡽⣎⢎⢆⢣⢱⠸⡰⡱⡸⡐⡌⡊⡎⡆⡕⡜⢌⢎⢆⢇⢇⠕⠨⢪⢪⢻⢗⣟⣿⣯⣷⣿⣯⣿⣯⣿⡿⣟⣿⣽
⡳⡵⣳⣳⣻⣿⣻⣷⣿⣿⣿⣽⣾⣿⣾⢷⣿⣟⣿⣿⣟⣷⣿⣽⢾⢛⠣⡑⡐⡐⡐⡐⠄⡕⢌⠢⠑⢌⠊⢔⠡⢡⢃⠎⢕⢑⢸⢘⢜⠜⡔⡕⢅⠇⢮⣻⣞⣽⢽⢯⢷⢕⠥⡑⡅⢇⢕⢜⠔⡅⡣⢕⢌⠊⢎⢜⠔⢅⢇⢕⢅⢣⠡⠡⡓⣝⢽⣗⣿⣟⣿⣿⣽⣿⣯⣿⣿⣿⣿⣿
⢜⢽⡺⣿⣿⣻⣿⣟⣿⣷⣿⢿⣻⣽⣿⡿⣿⣽⣿⢷⣿⢯⣞⣪⡦⣱⢕⢐⠅⡊⠔⢀⠣⢊⢠⢂⠅⡂⡑⡐⠅⡪⡂⠪⡪⡨⠢⡣⡱⡑⡕⢜⢸⢨⢛⢚⢚⠚⠫⠫⠫⢓⢅⢇⢊⢪⠢⡱⡑⢌⢊⠔⡐⡱⡑⠜⡜⡌⢎⢪⢊⢆⠣⡑⡌⡌⡺⢜⡽⣻⢯⣿⣯⣷⡿⣿⣾⣿⣾⣿
⡸⣜⢼⢹⡫⡿⣟⣿⣿⣽⣾⣿⣿⣟⣯⣿⣿⣿⣽⣿⣯⢿⣾⢟⢅⠫⡐⢅⠪⡌⡐⠄⡃⡢⡑⠌⢊⢂⢎⠌⡢⠱⠀⢱⠨⡢⠱⡱⡘⡌⡎⢜⠰⡸⣝⢞⢜⠎⢎⢪⢸⢰⢱⡸⡨⡂⢇⢪⢘⢌⠢⠁⠈⡀⠁⠑⠨⡊⡪⡸⡐⢅⠪⢰⣱⡽⡌⣮⣮⣎⡯⣞⣷⣿⡿⣿⣿⣾⣿⣻
⡺⣪⣷⣷⣯⣮⢇⣗⢽⣿⣻⣿⡷⣿⡿⣿⡿⣾⣿⣻⣞⣟⢏⢊⡢⢱⢘⢌⢎⠆⡊⡐⡐⢌⢊⢊⠊⠌⠂⣊⡤⢥⢌⠐⢕⢌⠪⡢⢣⢱⠸⡨⠊⠊⠂⠁⠈⠈⡁⠐⢡⢳⢵⢝⡦⡣⡣⡑⡢⠪⡀⡊⢔⢌⡮⢀⢐⠸⡰⡱⡑⡰⡁⡣⣑⡻⣻⣜⡽⡿⣿⣷⣮⣗⣿⣿⣷⣿⣟⣿
⢽⣽⣻⣯⣿⣟⣮⣺⣺⢿⣻⣯⣿⡿⣿⡿⣟⣿⣾⢿⢝⢅⢧⠱⡱⡑⡕⠌⡎⠔⡐⡐⢌⠂⢅⠢⠠⠁⢰⠣⡪⡪⡨⠣⡑⢔⠱⡘⡌⢆⢣⢊⠀⡐⠠⣑⠡⣱⢸⢼⡰⡹⣮⣻⣺⢽⣎⣎⢌⠇⡎⣌⢫⠜⡊⡔⠄⢕⠨⡪⡢⠢⡱⡘⡔⣷⢹⣷⢿⣿⢿⣷⣿⡿⣷⡽⣷⣿⡿⣿
⢿⢿⣾⣞⢿⣻⣯⣿⡿⣿⣿⣿⢿⣿⢿⣟⣿⡿⡞⣍⣾⣻⣣⢗⢕⢱⢡⠑⠌⣂⠢⡨⠂⠌⠄⠌⢀⠈⢸⢨⢲⡙⠌⠌⢌⢆⢣⠱⡘⡌⡆⠕⡠⡈⠣⡙⡝⡪⡞⣏⢮⣞⣗⣗⡽⣽⣺⣗⢷⡱⡸⣘⢮⡳⡕⡕⡅⢕⢸⢸⢐⡑⠴⡑⡜⠽⣗⣿⣽⢿⣿⣟⣷⣿⣿⣿⡽⣿⡿⣿
⢿⣽⣳⡯⡯⣿⣟⣿⡿⣿⣿⣾⣿⣿⡿⣯⣿⠏⣮⣾⣳⢯⢣⢣⠣⡱⢡⠩⡊⢔⠡⠨⠨⡈⠄⡁⠠⠐⡀⠓⡜⡎⢕⢁⢂⢪⠰⠡⡣⢪⠨⡊⢜⣜⢖⣔⢦⣳⢽⣺⢽⣺⣺⢮⣻⡺⡮⡯⣗⣟⣜⢮⢎⡞⡮⡪⡂⢕⢸⠰⡐⣯⢯⢾⣼⣮⣮⢺⣿⢿⣻⣿⣟⣿⣯⣿⣟⣿⣿⣿
⢸⢹⢺⣻⢭⡻⣟⣿⡿⣿⣷⣿⢿⡾⣟⣯⢏⢮⠳⡣⢣⢪⢪⠢⡑⡕⡡⢑⢌⠢⡊⠌⡂⠂⠅⠄⡑⡐⡈⡐⠈⢝⢆⢅⢂⠂⡣⡃⡪⡂⢇⠪⡸⣪⡳⣕⡯⣺⢽⣺⢽⣳⢯⣻⢮⡫⡾⢽⡻⡺⣺⣝⡯⡯⡯⣎⢂⠪⡪⡸⢐⢿⣿⣻⣾⣯⣿⡕⣿⣿⣿⣟⣿⣟⣿⣽⣟⣯⣷⣿
⢱⢨⠢⡊⡪⡻⣯⣟⡿⣿⢷⡿⡯⡿⡳⡫⡪⡊⡎⡎⡎⡎⢆⢣⢣⠱⡈⡢⡊⡢⡑⡁⡂⠅⠅⢂⠂⡐⠐⠨⠈⠄⠃⢆⢐⠄⡱⠰⡐⢅⢣⠑⡌⡞⡮⣗⢯⣫⣗⡯⣟⡾⣽⣺⣳⡱⡡⢕⢱⢡⣷⣳⢯⡯⣯⠪⡐⡱⡱⡸⠨⣟⣿⣿⣻⣿⣻⡧⣿⣿⣾⣿⢿⣻⣿⣟⣿⣿⢿⣿
⢸⠸⡸⡨⢢⢊⢢⢑⠍⡝⢝⠞⡪⡚⡜⡜⡜⡜⡜⢜⢜⠨⡪⢸⢐⢕⢘⢌⠢⠢⡱⠐⠄⠅⡊⠄⢂⢠⡑⠈⠐⡈⢀⣆⠔⠈⢂⠇⡊⡢⡑⢅⠪⡪⡫⡾⣝⣞⡮⡯⣗⡯⣗⡯⡾⣝⡮⡧⣳⢯⢾⣺⢯⣻⡪⡁⠢⢪⠪⡊⡪⢿⣯⣿⣟⣿⣯⢿⣟⣿⣾⣿⣿⡿⣟⣿⣯⣿⣿⣿
⠰⡑⡅⡣⠣⡊⡢⢣⢑⢜⢔⢕⢕⢱⠱⡑⡕⡱⢨⢃⢆⠣⡘⡌⠆⡂⡢⡑⠌⢌⠢⡑⡁⡊⠄⠅⠢⢘⣦⡁⡂⠐⠠⢈⠣⠐⠀⠎⡪⠰⡘⡌⡪⡪⢯⡺⣵⡳⡯⡯⣗⡯⣗⡯⡯⡳⠙⠜⣘⢸⣙⣞⡽⡺⠐⡀⡣⢱⢱⢱⡪⣹⣿⣯⣿⣿⣽⣿⡿⣟⣿⣾⡿⣿⣿⡿⣟⣯⣿⣿
⠨⡢⡑⢜⢘⠜⡸⢘⢌⠆⡕⢔⡑⡔⢕⠡⡂⡊⡢⢑⠔⢅⢃⠢⢑⠐⠔⡠⢑⠄⡃⢆⠕⡨⡘⣬⠌⡂⣳⣷⠄⠅⡘⠐⡀⠂⡁⠌⡊⢎⠔⢕⢌⢪⢳⡹⣪⢞⡽⣝⢮⣻⡺⣜⣖⢮⢏⠯⡪⣺⢺⡪⠎⠠⢐⠐⡌⡪⡢⣻⣯⣒⢿⣯⣿⣾⣿⣷⣿⣿⣿⣟⡿⣿⣷⣿⣿⣿⡿⣿
⢌⢂⠪⠨⡂⠕⢌⠢⡢⡑⢜⢐⢑⢌⠢⡑⢔⠔⢜⠰⡑⡑⠄⠕⡠⠡⠑⠄⠅⡂⡪⡂⡣⣫⢷⢹⣣⡊⠔⣿⢺⣲⣄⡡⠀⠅⠠⢂⠪⡨⡊⡪⡪⡊⡆⢝⢜⢵⢝⢮⡳⡳⣝⡞⡮⡣⡣⡣⣣⡳⡝⢼⠀⢂⠂⢅⢣⢣⢹⣽⣿⢿⣞⣿⢿⣽⣾⣯⣿⣿⣾⣿⣿⢿⣽⣿⣽⣿⣻⣿
⠔⡨⠨⡨⢂⠣⡑⡑⢔⠨⠢⡑⢔⠢⠱⡘⢔⠡⠅⢕⠨⡐⢡⢑⠠⠡⠡⠡⠨⠢⡱⡱⡽⣽⢿⡷⣝⢗⢅⠫⢫⠳⡙⡪⢀⠠⢑⢀⢂⢒⠌⢆⢣⢣⢝⠰⡐⢔⠩⡑⠹⢹⢪⢞⢽⡹⣝⣞⢞⢎⢎⢽⣷⠡⡈⢔⢕⢕⢽⣷⣿⣿⣿⣽⣿⣿⢿⣻⣿⣾⣿⣾⣿⣿⡿⣿⣽⣿⣜⣮
⢈⠢⡑⠔⡡⠊⠔⡨⠠⠡⠡⠨⢐⠨⠨⡐⡐⡡⠡⡁⡢⠨⢂⠂⢌⠌⢌⠌⣜⣼⣽⣺⡝⡾⡹⡹⡸⣝⢜⢮⡲⣕⢬⠢⡂⠆⡂⡂⠢⠀⠕⡑⡌⡪⢪⢱⢡⠣⡑⡌⡊⣂⠂⠉⠘⠊⠃⠓⣡⢇⣗⢽⡗⣕⠀⡎⡎⡦⣿⢿⣷⣿⣯⣿⣿⣾⣿⣿⡿⣷⣿⣷⣿⣷⣿⣿⡿⣯⣿⣿
⠠⡑⠌⢌⠢⠑⢅⠢⠡⠡⠡⡑⠄⠅⢅⢂⠢⠨⢂⠢⢊⠌⢄⠅⠅⢌⢂⢣⡮⣷⡿⡎⡎⡞⡜⣜⢕⢗⡽⣕⢗⡕⣗⢽⡹⡵⣢⢦⢅⠅⢌⠐⢅⠇⡇⡎⡪⡪⡊⡆⢕⠔⠀⠀⠈⠌⡨⢐⠨⢙⢎⣟⣯⠇⢌⢎⢂⢻⣽⣿⢿⣷⣿⣿⣾⣿⣯⣿⣿⢿⣯⣷⣿⣯⣿⣷⣿⣿⣿⣻
⠨⠢⡑⡡⠨⡊⠔⢌⢊⠌⢌⠔⠌⢌⢂⠢⡡⡑⡐⢅⠅⡪⢐⠡⡑⢕⢨⣾⡿⡟⢟⠕⡕⢕⠝⠜⡜⣕⠧⡓⡯⡺⡵⡫⣞⣝⢮⡳⣝⣝⢔⢅⠅⢇⢇⢇⢇⢎⢪⢪⠢⡃⠀⠀⠁⠀⠂⠢⠡⡑⡰⡐⠝⢄⠕⢌⢂⢂⢳⣿⣿⡿⣷⣿⣷⣿⣯⣿⣾⣿⣿⣿⣻⣽⣿⣽⢯⣾⣿⣿
⠨⡈⡂⡪⠨⡂⠕⡁⡂⡊⢔⢬⠮⣒⣥⢷⠻⡐⠅⢕⠨⢂⠢⡣⢑⢡⣟⣿⠘⠜⡌⣆⢮⢢⡕⣗⡬⣢⣣⡣⡧⣕⢕⣍⡪⡨⡣⡫⣞⢮⡳⡕⡅⡣⢣⢣⢣⢣⢣⠪⡒⡄⠀⠁⠀⠁⡀⠈⠈⠰⡐⢜⠨⡢⢃⢅⠪⡐⠼⣿⣷⣿⣿⣿⣾⣿⣽⣿⣻⣽⣷⣟⣿⣿⣟⣿⣿⣿⣯⣿
⢐⠰⢐⠐⢥⣶⣷⣶⣾⡾⣾⡾⡝⡫⠨⠢⡑⢌⠪⢐⢈⠢⡃⠪⣐⣵⣟⠭⣊⢎⢇⢧⢳⢱⢝⢮⡺⣕⢗⡝⣞⢮⡫⣞⢵⡻⣮⣲⡡⣓⡝⣎⢧⢑⢅⢇⢇⢇⢇⢇⢕⢜⢄⢑⠈⠀⡀⠄⠀⠄⠌⡢⢱⢡⢑⠔⡑⢌⠪⡹⣿⣽⣷⣿⣷⣿⣟⣿⡿⣟⣿⣿⢿⣽⣿⢿⣽⣾⣿⣿
⠐⠌⡂⢅⢹⣯⣷⣿⣷⣿⠟⢕⢼⢐⢑⢑⠌⡐⠨⢐⠐⢅⠊⢌⣾⣟⣧⡣⡣⡱⢹⢸⢸⢜⢮⡺⡜⣞⢼⡺⣪⢞⠮⣎⢗⢝⡞⣎⢯⡳⣝⢮⡳⡥⣱⢰⢑⢕⢕⢕⢕⢌⢆⢇⠅⢅⠀⡀⠄⠀⢁⢊⠢⡑⢅⠕⡅⢕⢱⠐⡙⣿⣿⣽⣾⣿⣟⣿⣿⣿⡿⣿⣿⢿⣿⢿⣿⣟⣿⣾
⠨⠨⢂⠅⣞⣿⣻⡽⡳⣡⣳⠫⡑⡐⡡⠂⠢⠨⡈⡂⠅⢅⢊⣾⢿⢍⢇⠇⢇⢓⢕⠇⡗⢵⢱⢕⢵⢝⡜⡜⡌⡇⡏⡎⡮⡳⡹⡪⡳⣝⢮⢧⡳⣝⢮⡳⡅⡎⡜⢜⢜⢜⢌⢆⠝⡔⡡⡀⠄⢀⠀⠑⡅⢕⡐⢅⠣⡣⡱⡈⡢⢊⠻⣟⣯⣿⣟⣿⣷⣿⡿⣿⣻⣿⣯⣯⣿⡿⣟⣿
⠨⠨⢂⢊⠝⢝⣱⣵⣾⢯⣦⢊⢐⠔⠠⠡⠡⠡⢂⢊⢌⠢⣹⡷⡹⡐⡅⢕⠅⠕⠔⡑⢌⠢⡃⢕⠸⡘⢜⠑⠅⡃⠣⡑⢌⠪⡊⡣⢫⢪⢎⡇⡧⡳⡕⣝⢮⢳⡑⡅⢇⢧⢱⢪⣪⢲⣳⢸⢨⠢⡐⡀⠘⢔⠜⢌⢊⢎⢎⢆⠊⡆⡇⡻⣿⢿⣟⣿⣽⣾⣿⣿⡿⣟⣿⣟⣿⣿⣿⣿
⢈⢪⣲⣳⣳⣿⡾⣿⣾⡟⡓⡐⡐⠌⡊⠌⢌⢊⠔⣰⠢⣱⣿⣷⡑⢌⠌⡂⠁⠄⠡⠈⠄⡁⠂⡁⠅⠨⠠⢈⢐⢀⠡⡐⡐⢔⢐⠌⡐⢐⠐⢍⢊⠇⠏⡎⡮⣣⢳⡘⡌⢎⢖⠅⢗⡯⣞⢵⡪⣊⢆⠠⠀⠂⡣⡱⡘⡌⡎⡎⣮⣔⢕⢕⢎⢿⣿⡿⣿⣻⣯⣷⣿⡿⣿⣿⣻⣷⣿⣿
⢐⢽⡿⣿⣟⣯⣿⠿⢑⢐⢐⠌⡐⡡⢂⢑⢐⢐⢌⡯⡨⣾⣿⣯⣿⣆⠁⠄⠁⠌⢈⠠⠁⢀⠂⠄⠌⢌⠌⠆⠕⠌⠪⠐⠅⠃⠆⠕⡐⡐⡈⠠⢀⠈⡈⠐⠩⢊⢇⢳⢸⠨⢪⢪⠢⡫⣞⢵⡫⣞⡔⡅⡂⠀⠐⠜⡌⡪⢪⢪⢺⣿⣳⡱⡱⡕⣕⢿⣿⣿⡿⣟⣯⣮⣫⣿⣿⣻⣽⣾
⢷⣗⣟⢿⡻⢏⠅⡑⡐⠔⡐⢌⢐⢐⢐⢐⢐⠔⡘⠅⣾⣿⣯⣿⢾⣿⡆⠀⢁⠠⢀⠠⠐⡐⢈⠌⠨⠐⠈⢈⢀⠅⡢⢒⠔⡢⡂⡂⠄⠠⠈⢈⠂⡂⡂⡡⠐⢀⠐⠡⢊⠪⡢⢑⢕⢕⢽⣕⢯⢞⢮⣣⢅⠨⡀⠀⢕⢜⢸⢸⡸⣿⡿⣟⣎⢮⡪⡪⢝⢷⣿⣿⣯⣾⣿⣿⣻⣿⣿⢿
⣿⣿⢿⡯⠃⢅⢂⢂⢊⠌⡐⡐⡐⡐⡐⡐⡐⡐⡰⣵⣹⣳⣷⡩⠛⠓⠠⠈⠄⠂⠄⠂⠡⠐⠀⠐⢀⢐⠨⢂⢑⠌⡢⢑⢌⠢⡑⠕⡅⢅⠀⢂⠠⠠⢀⠂⡁⢂⠐⠠⠀⠌⢌⠢⡑⡕⡕⠵⡯⣯⣳⡳⡳⠀⢕⠅⠄⢣⠱⡱⡱⣻⣿⣿⣽⣯⣿⣮⡪⡪⡎⡿⣿⣻⣽⣾⣿⣿⣾⣿
⣿⣾⡟⡐⡡⢁⢂⠢⠂⢅⠂⡂⡂⡂⡂⣂⢆⢢⣿⡿⣿⡿⣿⣿⡄⠈⠄⠁⠌⠀⠂⠁⠐⠈⡀⠅⢂⢐⠨⡐⡐⠅⢌⠢⠢⡑⠌⢌⠌⡢⢃⠢⠨⠨⢐⠠⠂⠄⠌⡀⠡⠐⢀⠁⠊⢜⢌⠇⡏⣞⢮⣞⡝⠀⡧⣃⢇⠌⡪⡪⡪⣙⢯⣿⣷⣿⣷⣿⣻⣮⡪⡪⡪⡝⢿⡿⣟⣷⣿⣟
⣿⣻⢂⢊⠄⢅⠂⢅⠑⠄⠅⡂⡂⡂⡢⣿⡂⣾⣟⣿⣿⢿⣟⣿⠂⡈⢀⠈⡀⢈⠀⠁⢀⠁⠠⠐⡀⠂⠌⡐⡨⠨⢂⠅⠕⡨⠨⢂⠑⠄⠡⢑⠁⠅⢂⢑⠈⡈⠢⡐⡠⢈⠠⠀⠅⡕⢌⠪⡌⡲⡙⠎⠎⢠⡻⣪⢦⢑⠈⢎⢜⢔⢽⣿⢿⣾⣿⣾⣷⣿⢿⣮⢪⢪⢪⢪⢻⢻⢿⣟
⣿⢯⠐⠄⠕⡠⠑⠄⠅⢅⠕⡐⡐⠔⣽⣿⢊⣿⣟⣿⣽⣿⣟⣷⠀⠠⠀⠠⠀⠠⠀⠐⠀⠄⠁⠄⢂⠡⠑⡐⠄⠕⡠⠡⡑⠠⠡⡑⠨⠨⠐⠠⠡⠈⠄⡐⢀⠨⠂⠢⡈⡢⠨⢂⠅⡇⢌⠪⡸⡰⡘⡔⡈⡮⡺⣝⡵⡣⡃⢅⢣⢱⢸⣿⣿⡿⣷⣿⣯⣿⣿⣿⣷⣕⠧⣇⢇⢇⢇⢏
⡿⡯⡈⠪⠨⠠⠡⠡⢡⢑⠰⡐⡌⢌⣿⡿⣸⣿⡿⣿⣟⣯⣿⣿⣿⣶⣌⡠⠐⠀⠐⠈⠀⠄⠂⠐⡀⢂⠡⢐⠈⠌⡐⠡⡂⠅⠅⠂⠅⠡⢂⠐⢀⠈⠐⠀⠄⢊⠢⣁⡐⠄⠅⠅⡢⠅⢑⠱⡈⢎⠪⡊⡎⡮⣪⣪⢺⡘⡼⣅⠪⡸⡨⢿⣷⣿⣿⣯⣿⣯⣷⣿⣯⣿⣿⣵⣯⣺⢮⣪
⣏⠢⠨⡊⠌⢌⠌⠌⡂⢆⢕⢸⣷⢁⢻⡯⣺⣿⢿⣿⢿⣿⣻⣷⣿⣷⣻⣿⣶⣌⠄⠐⠀⠂⢀⠁⠄⢂⠐⡐⠨⢐⢈⠢⠨⡘⠨⡈⠌⡈⠄⡀⠄⠀⠁⢂⠀⠀⠄⠁⡘⠸⢸⢨⠊⠄⠄⠁⢊⢪⢑⠅⡇⡗⣕⢗⣳⡹⣝⢮⢆⢊⢆⢑⠻⣯⣿⣯⣿⣟⣿⣯⣿⣟⣯⣿⣟⣿⣷⣟
⠆⢅⠕⡐⡡⠡⡈⡂⠪⡐⢴⣹⣿⣧⢂⠫⣺⣿⣿⢿⣿⢿⣟⣿⣽⣿⣻⣿⡍⠁⠀⢀⠐⠀⠠⠐⠈⠄⠂⠄⠡⢂⢐⠨⢐⠨⢐⠨⠐⡀⡂⠄⠠⠀⢈⠠⠀⠠⠐⢀⠠⠀⠀⡀⠌⠢⠡⠡⡀⢐⠱⡁⢧⢇⢯⢳⠵⣝⢮⣫⢳⡢⢊⠔⠱⡨⠻⣿⣽⣿⣟⣯⣿⣿⢿⣿⣻⣿⣯⣿
⡍⡂⡢⢂⢊⠔⡐⠌⡂⡊⢾⡮⣾⣿⣷⣌⢺⣿⣻⣿⡿⣿⣿⢿⣟⣿⣟⣿⡇⠈⠀⠠⠐⠀⠂⢀⠁⢂⠁⠌⠐⡀⠂⠌⠠⠨⢐⠨⠠⢀⠐⢈⠐⠀⡀⠐⠈⢀⠀⠢⢐⠀⠅⡀⢀⠀⠈⠨⢐⠀⡘⢌⢪⡳⣹⢪⡫⣎⢧⢳⡣⡇⡕⡌⡌⠢⠨⢌⢛⣯⣿⣿⣟⣿⣿⢿⣻⣯⣿⣿
⡒⢼⣂⠢⠡⢂⠊⠔⡐⢌⢺⣷⢹⣷⣿⣿⣅⡻⣻⣯⣿⣿⢿⣿⢿⣿⣻⡟⠀⡈⠀⠂⡀⠂⠈⢀⠠⠐⠀⠌⡀⢂⢈⠈⠨⠐⡐⠠⢁⢂⠐⡀⠌⠀⠀⠈⠠⠀⠄⠨⠂⢅⢂⠐⡐⡐⡀⠀⡂⡒⠢⠢⡡⡫⡎⣗⢝⣜⣎⢧⢳⢕⣝⠮⡪⠠⢁⠑⡔⣿⣿⣯⣿⣿⣻⣿⣿⡿⣟⣿
⢌⢽⢧⠨⢊⠔⢡⡑⡐⢄⠹⣿⣧⡻⣿⣽⣷⣝⣷⣽⡻⡿⣿⢿⣿⢿⡏⠀⠄⠀⡀⢁⠠⠀⡁⠀⠄⠐⠈⠀⠄⠠⠀⠌⡀⠂⠐⠈⠄⠂⡂⠂⢄⠀⠄⠁⠠⠀⠠⠈⠄⢅⢐⠠⠐⢐⠨⠠⠀⠕⠊⠡⡂⢇⢟⢮⡳⡕⡧⣫⢺⡸⡸⣕⢕⡕⢄⠐⢌⢻⣽⣿⣽⠻⣟⣯⣷⣿⣿⣿
⢐⠌⢿⣕⢐⠸⣔⢿⣔⠄⠅⠽⣾⣷⣝⢿⣿⣻⣞⣿⢿⣿⣾⢿⣽⣟⣿⣆⠐⠀⠠⠀⠠⠀⠔⠈⢀⠁⡈⠠⠐⠀⠂⠐⠀⠅⠨⠐⠈⠠⠠⠑⠠⠂⠄⠂⠀⠀⠄⠨⠀⢕⠐⡀⠂⠀⠁⢅⠑⠄⠂⠨⢨⢊⢗⣕⢗⡝⣎⢮⢣⡣⡯⣪⢳⡱⢅⠂⡐⠝⣿⣟⣯⡣⣿⣿⣿⡿⣟⣿
⢐⠅⠕⡻⣕⠌⣻⢷⢽⢮⡨⠂⠝⣿⣽⣮⡻⡿⣿⣻⣽⣿⣽⣿⣿⣻⣿⠝⠀⠐⠀⡈⠠⢈⠐⢈⠀⠠⠀⠂⠐⠈⠀⡁⠌⠀⠅⠌⢐⠀⢂⠈⠨⠈⡀⠀⠀⠐⠀⡂⠡⢐⠠⠀⠅⡈⢀⠂⠁⠅⠂⠌⡐⢅⢇⢗⡕⡧⡳⡱⡣⡣⡳⡱⡱⡑⢅⠂⠠⢑⠐⢝⢿⣿⣿⢿⣷⣿⣿⣿
⠐⢌⠌⡢⠙⢜⢈⢿⣻⣷⣵⡡⠑⠌⢟⣿⢿⣯⣽⡻⡿⣷⣿⣷⢿⣻⣿⠀⠄⠀⠁⡀⠠⠀⠂⡀⠂⠁⠄⠁⡈⠄⠁⢀⠀⠡⠐⠈⠠⠈⠄⢂⠀⡁⠠⠀⠀⠀⠂⠠⡁⠐⠄⠨⠐⡀⠐⠠⡱⠡⡁⠌⠄⠕⢜⠸⡘⢜⠨⢌⠪⡘⢌⢌⠢⡑⠔⠈⠀⠌⢌⢐⠕⣿⣿⢿⣟⣯⣿⣿
*/
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("popcnt,avx2")
/*
⣿⣿⣟⣿⢯⣿⣺⡴⡵⡝⣞⢵⢫⡳⣕⢧⢳⢱⢣⢳⠱⡱⢱⠱⡝⡹⡘⢌⢎⠎⡪⣻⠌⢮⢻⢺⣝⢕⡏⡎⣞⡝⠔⢅⢫⢚⡜⡮⡪⡪⡯⣺⢝⣮⡳⡑⠌⠢⢂⢂⢂⠂⡂⡐⡐⢐⠐⠠⢂⢂⢂⢢⠢⢃⡂
⣿⣿⣽⣿⣻⣯⣷⣟⡷⡽⣜⢕⢏⢮⢣⢳⠱⡱⢑⠅⡓⢘⠈⠌⢜⢜⣐⢅⢪⡂⡎⡜⠨⡃⣇⢷⢱⡹⡜⡎⡢⣪⠮⣞⡮⢷⢽⡚⠯⡯⡯⣗⡯⣞⡞⡌⠨⡈⠄⢂⠂⠌⡀⢂⠈⠄⠨⠐⡐⢔⢐⢄⠝⢄⠇
⣿⣿⣿⣽⣿⣽⢾⢹⢸⢨⠢⡃⢇⢇⢃⠢⡁⠢⠐⠠⢐⢐⢨⡸⡸⣱⢃⠳⡯⣚⢽⡯⡳⡄⢣⢳⢣⢫⢺⠨⣾⣯⡫⣟⢮⢣⢏⢜⢮⢯⣫⣗⡯⣗⢯⢢⢡⢢⢨⠠⡈⢄⢂⢢⠡⡑⢌⡂⢎⠰⢂⠇⡬⣢⡣
⣿⣿⣿⡯⣟⢜⢜⢜⢜⢜⠜⡌⡆⡕⠈⠰⣐⠡⠨⡂⢅⠍⠆⠏⡊⣗⢵⡣⡝⠧⢯⢺⢺⢯⢸⢰⢣⣣⢳⣱⣿⢝⠙⡊⣍⢕⣕⢯⢏⣗⢵⣣⢯⡳⣝⠌⠌⢊⠪⡊⠎⡢⠑⠔⢅⣂⡢⢪⢘⠸⡐⠅⡟⡎⡢
⣿⣿⡿⣹⢜⡎⣇⢧⢣⡣⡇⣇⠎⡂⣕⡜⡆⠥⡑⡌⡔⡌⡪⡊⡆⡖⡱⡙⡜⡹⡰⢐⢜⣟⢮⡓⣝⢼⢕⣗⢿⢵⡡⠕⡕⡵⡪⡮⣣⢗⡽⣪⡻⡺⡸⢬⢪⡔⡤⡣⢣⢢⢌⠌⡔⡢⢂⠡⢂⠡⡈⡆⡪⢈⠔
⣿⡿⡽⡵⣫⢞⢮⢎⢗⢜⢜⢌⢌⢮⢣⢣⢣⢫⢊⢎⢌⢎⢪⠪⡚⡘⢜⢎⢎⢔⠨⡰⡕⣝⣗⣝⢮⡳⣯⡯⡗⡳⣹⣪⡪⢮⢺⢸⢪⢳⢝⢵⢹⢸⡸⣱⡑⡗⡕⡔⠄⠕⠕⡱⢕⣑⠡⡊⡊⠢⡸⡐⠌⠢⡑
⡿⡽⡽⡽⡵⣫⢯⡺⣝⠮⠱⡰⢍⢮⢪⡪⡪⡪⡪⡊⡆⡣⡕⡕⣕⢳⠡⡑⠱⣐⠨⡚⠜⡈⢾⣪⢗⡯⣗⡯⢈⠚⡎⡎⠮⢕⢕⢕⢜⢔⢕⢑⢅⢇⡞⡕⣕⢬⢹⡘⢌⠆⢕⠨⠐⡈⡪⠌⡜⠬⡒⡐⢕⠅⡎
⣿⣯⣟⡮⣯⣳⡫⡯⣞⣝⡽⣸⣺⡱⣱⢱⢕⢕⢕⢜⢜⢜⢜⢜⢔⡵⡪⡠⠑⠄⢅⢈⠂⡂⢀⠹⢵⣻⢋⠠⡂⢍⢪⠪⡍⡧⡹⡸⣐⢢⢅⣕⣕⢯⢪⢎⢮⡪⡎⣎⢦⡱⡒⠜⢔⠔⡐⡱⡐⠅⡢⡪⢨⠪⡈
⣿⣿⡿⢏⢚⢪⠯⡻⣺⣺⢽⣺⡷⣝⢮⢮⡳⣝⢵⡳⣕⢧⣳⣝⣵⡳⣍⠮⢨⠨⡂⡢⢨⠐⢔⢼⢼⢷⡵⡵⡵⡳⡱⡕⡇⡇⡇⡇⡧⣳⢝⡮⣎⡮⣳⣫⢳⡱⡱⡸⣲⠱⢨⢪⢐⢌⠤⡱⢑⡑⡅⠜⡐⠕⠨
⢇⢇⢣⢣⢱⢡⢱⡑⡅⡇⡏⡭⡍⡍⡏⡳⣛⢺⢹⢺⢝⠟⠞⡚⣺⢽⡪⡎⡐⢕⢜⢜⢔⢍⡆⡮⣌⢪⡊⡎⡎⡮⡪⡳⡹⣪⢪⡺⣜⢮⡳⣵⡳⡯⡳⡣⡳⡸⡸⡜⣮⣣⢑⠔⠨⣐⠱⡈⡎⠆⡌⢌⢂⠣⡡
⢇⢧⢳⡱⡕⣇⢧⢣⡣⡣⡣⣃⢏⢞⠮⡺⣜⢼⢱⢱⢱⢡⡣⣳⣳⣳⡽⣕⢵⢱⡪⣪⢪⡪⣎⢗⡵⡳⣝⢼⡪⡮⡪⡣⡯⢮⡳⣝⡮⠗⢯⢗⢏⢏⠮⡪⡌⡮⣪⢞⣞⢦⠱⡐⠅⡌⣊⢀⠃⠇⠪⢐⢅⢕⠠
⡏⡮⡪⣪⢺⢜⢎⢧⢫⢎⢗⢜⢼⢜⡜⣕⢕⢝⠺⢵⢳⣗⣯⣷⢿⢵⢯⡲⡑⡱⢙⢎⢗⢽⡺⣽⡺⣽⢺⣳⡻⣪⢯⡣⣏⢗⢯⢳⡹⠀⢂⢁⢇⢇⢗⢕⢝⢜⢮⡺⣼⢳⠱⡁⢇⢆⢕⢰⠑⡡⠃⠅⡒⠐⢅
⡺⡜⡮⡪⣎⢮⢺⢸⢸⢪⢎⡗⡕⡧⡫⣪⢞⢜⢜⢜⢔⢎⡪⡎⣏⢝⢵⢱⡢⣕⢌⢎⢜⢢⢣⢣⢕⢵⢹⢔⢝⢎⢕⢕⢕⢕⢕⢕⢵⢡⢦⠀⠫⡪⡪⡎⣇⢗⢗⣝⣞⡑⢅⠪⢑⢡⠡⠢⡘⢄⢃⠅⡡⢑⢔
⢼⡹⡪⣇⢧⢳⡱⡕⡧⡳⡱⣕⠵⡕⡽⣜⡜⣎⢎⢎⢮⢪⢮⢺⡪⡣⡇⡗⡝⡜⣕⢗⢮⠮⡦⣣⢇⢧⢣⡣⡳⡹⠜⢜⢸⢨⡪⣑⠵⠳⡕⣕⠀⠣⡣⡣⡣⡯⣳⠍⠄⢎⢔⠪⡂⠢⡡⣃⢣⠪⡡⠪⡘⢬⢪
⢮⡪⡳⣕⡝⡮⡺⡹⣪⡫⡫⡎⣗⢝⢎⢗⢝⢚⢎⢗⠵⠵⠵⣕⣵⡣⡇⡇⡇⣇⢧⢣⢳⢹⠪⢊⢝⢮⢧⡣⡺⡸⡸⢌⠜⢆⢂⢎⠍⢕⠵⡡⡃⢅⠨⡊⢇⠯⡣⢪⢥⠡⡑⣕⢜⢜⡰⢰⢁⡖⣎⠕⡌⡌⡢
⡗⡝⣞⢜⢮⢳⢝⣝⢼⡪⡯⣺⢸⢪⢺⢸⢸⢨⢢⢣⢣⢫⢱⢱⢲⢱⠹⡹⢺⢪⢮⢮⣣⢗⡭⣢⣪⡺⡇⡇⡣⡃⢇⠣⡃⠕⢔⢐⢜⢌⢪⠂⢇⠣⡂⡈⢆⢑⠨⢡⠕⣕⡕⡕⡭⡣⡪⠊⠜⡮⡕⠌⢆⢊⢆
⡮⡫⡎⡗⣕⢇⣗⢼⡸⡜⡎⡮⡪⡣⡳⣱⢱⡱⡱⡱⡕⣝⢎⢧⢣⢇⢇⢕⢕⢱⢹⢸⢪⠫⣓⢕⢗⢝⡜⡬⢪⢸⠰⡱⡸⡸⢊⢎⢆⠆⡕⢌⠢⡒⠅⢄⣂⢆⣎⢂⠑⠅⣃⠳⡒⣕⢘⢬⢊⠄⢍⠪⢐⠡⢃
⡮⣫⢮⡻⣜⡕⣗⢵⡹⡜⡵⡹⣚⢝⢞⠮⣗⢗⢽⣜⢮⡪⡞⣕⢇⢧⢱⢸⢰⢱⢱⡱⡱⡑⡕⢕⠡⢣⠓⠛⠚⠲⢵⢱⠜⠒⠓⠲⣐⠗⠓⠒⠓⢲⢍⠒⢒⠒⣌⠱⢕⡗⠓⣖⢸⠚⡪⡒⠚⠚⠓⠣⡀⠕⡁
⣇⢗⢵⢹⢸⢪⢎⢧⢳⢹⢕⢽⢸⡸⡸⡸⡸⣸⢪⢮⠳⡝⡾⡮⣓⠳⢝⢼⢪⠮⡮⣪⢎⢮⡪⡲⡨⡸⡀⢪⢻⠀⢸⡇⠄⡏⢵⠁⢸⡊⠈⢋⠛⡯⣄⠨⠉⡒⢮⡊⢆⡇⠄⠉⠄⠂⡅⠆⡈⠛⠙⡧⢂⢣⢐
⡪⣫⢳⡹⡪⡇⡗⣕⢵⡱⣕⣝⢼⡺⣜⢎⢮⢳⡣⡏⡎⡎⡪⢪⠪⡙⡎⡦⢕⢕⣘⢪⢪⢣⢳⢽⡸⡪⡂⢈⢉⣄⠞⡣⣀⠍⢉⣠⢎⠇⢈⠉⡉⢹⢄⠌⠋⣀⡼⡸⢨⡇⠐⣏⢩⠀⡎⡅⠈⡉⢉⢱⡕⢜⠲
⡹⡜⣎⢮⢳⢱⢝⢜⠜⡜⢝⢺⢳⢯⢮⣗⣝⢜⢮⢎⢇⢇⢇⢇⢇⢇⢇⢎⠪⡪⠢⢑⠱⠥⡱⡢⢇⡇⡎⡂⡂⠪⡢⣘⠄⠝⠰⠰⠐⢕⠅⢇⢜⢅⢅⠫⡉⡢⠢⢃⠣⢨⡂⡎⡜⡆⡑⠬⡑⡜⢔⠐⡍⡎⣜
⢞⣎⢮⡪⡮⣪⢪⡢⡣⡪⡸⡨⡪⣊⢳⢓⣗⢯⣗⣗⣭⡳⣝⣜⢮⣪⢮⡪⣪⢪⢪⢂⢏⣽⠎⣂⢢⡃⡕⢅⠢⡑⢴⢑⠄⡃⢅⢂⢅⢕⠸⣊⢂⢁⢆⢊⡢⢭⡘⢆⢍⠆⢧⢑⠔⢬⡡⠃⡎⢢⠡⠱⡂⠮⡇
⢵⣳⡳⡱⡣⠧⡧⣳⢱⡱⡕⡵⡱⢢⢑⠕⡱⡹⡰⢕⡷⣝⢮⢎⢎⡎⢎⠇⡳⡙⡪⡚⡙⢎⡪⡘⢄⢃⠌⡢⢱⠚⢳⡵⠚⢚⢶⠓⠢⣢⠓⢳⢬⠒⠃⠒⠣⣳⠚⢳⠞⠚⣶⠓⢳⠓⢊⠚⢔⡱⡨⢊⡰⡨⠨
⢗⢗⡕⢕⢕⠕⡕⣳⢹⠪⡕⡝⡼⡌⡆⡕⡱⡨⡊⡇⡇⢕⢏⢮⢣⡺⡰⢕⢲⢑⠔⡅⢊⠢⢃⢂⠢⠡⡨⡈⣲⠀⡘⠠⠐⡕⢼⠀⡂⡘⢀⢺⡇⠠⡏⣳⠁⢸⡔⠘⡀⡆⢉⠀⣟⢲⠋⢂⠮⡒⡅⡅⡪⠘⡨
⡇⢏⢞⠢⣕⢜⠜⡎⢎⡪⡪⡚⡜⡜⡜⡜⡜⡔⡕⡜⡌⠊⡌⣝⢾⡸⡱⢅⠝⣔⠱⢨⠘⠌⢢⢐⠕⡣⡑⡐⡸⣀⣰⠵⣈⣘⣽⣀⡯⢢⣠⣸⠱⣄⡩⣑⡨⢎⢣⣐⣰⢣⣀⣼⢰⢺⣉⣹⠰⢡⠪⡐⠄⠕⡆
⡊⡪⣪⢺⠰⡅⣣⠪⣸⢰⠪⡘⡌⡎⡪⢪⢺⢸⢸⢑⡕⡕⡕⡗⡕⡑⡜⠬⠨⡢⡑⡑⡅⢅⠢⠑⠌⡠⡒⠩⡂⠢⡰⢑⠡⡑⡅⢆⠪⢈⢂⠪⡐⠄⡂⡂⢌⠌⢑⠼⡰⢱⠑⢎⢇⣗⢅⢇⠊⠬⡘⠌⡌⡎⢜
⠆⢕⢕⢵⢱⢑⠢⡹⣰⢱⢱⢱⢑⡑⡅⢕⠅⡇⡅⡇⢇⢫⠪⡂⡕⢅⢢⡡⢃⠇⠌⡢⢅⠑⡌⢌⢢⠡⠨⡊⢌⢣⠸⡐⡂⡣⠣⡨⠊⢜⠆⢕⢌⠌⡢⡉⡆⡕⡀⣂⡊⡎⠎⢎⢌⢺⡨⡂⡎⠎⠄⢇⢒⢢⠣
⠩⡒⢕⢹⢘⢌⢎⢎⢎⠮⡸⡨⡲⡱⠡⡣⡑⡌⡢⡹⢨⠪⡊⢔⢑⠅⢅⢊⠔⡌⢌⠂⢅⢪⢐⢢⠢⢱⠱⡐⡐⠅⡣⠅⢆⠜⡘⡐⢩⢃⠝⡠⢪⡪⣊⠜⢅⠆⡊⡆⡢⡹⡎⡦⠑⠥⡱⡌⣂⢣⠩⡐⡘⠔⢵
⠢⢊⠌⡎⢎⢎⠎⡎⡢⢇⢕⢱⢨⠪⡱⢑⠇⢕⢲⢘⢌⠪⡨⣂⢊⠢⡑⠔⡡⡂⠕⢌⠜⡐⢌⢃⡙⢄⢂⠅⡖⢑⠰⢡⠃⢎⡐⡊⡢⠂⠇⠆⢕⢘⠆⡕⡑⡑⢅⠢⡪⡨⠝⡪⠊⠔⡰⠡⡐⠡⠁⡒⣥⢪⢵
*/
using ll = long long;
//#define int long long
#define forn(i,n) for(int i=0; i<(n); ++i)
#define pb push_back
#define pi pair<int,int>
#define f first
#define s second
#define vii(a,n) vector<int> a(n); forn(i,n) cin>>a[i];
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll inf = 1e9;
const ll mod = 1e9+7;//998244353;
/*
⣿⣿⣿⣻⣿⣿⣿⣿⣿⣿⢿⢂⢂⢂⢂⠔⡐⡐⢔⢔⢡⠪⣛⣿⣿⣿⣿⣿⣿⣿
⣿⡯⣿⣯⣿⣯⣿⡿⣾⢝⢑⢐⢐⠔⢔⢱⢘⢌⢆⡧⣣⡣⡳⡜⡽⣾⣿⣯⣿⣷
⣽⣿⡿⣿⢽⣾⣿⡻⡋⡂⢆⢑⢜⠸⡸⡘⡜⣜⢜⢜⢜⢜⢕⢕⠱⡽⣿⣾⣿⣽
⢵⣻⣿⣯⣳⣿⣟⡯⠪⠐⠌⡂⢅⠇⡕⢕⢱⡿⡜⡸⡰⡑⢅⢇⠣⢝⡿⣯⣿⣿
⢼⣽⢻⣿⣻⣷⡷⡩⡱⢁⠣⢘⠄⢕⠜⠜⢒⢂⢇⣎⢆⢌⡄⢕⢁⡳⣫⣟⣯⣿
⠿⣽⣿⣿⣯⠧⡗⡕⢔⢐⢈⠐⢍⠢⡃⡣⡭⣽⣺⣺⡳⣜⢮⠸⣰⣮⣻⣿⣿⢿
⠪⡸⣘⢓⢕⠕⢕⠅⠕⡐⡐⢌⢈⠔⢌⢢⡫⣞⡾⡲⡪⡯⠇⢕⢼⣿⣾⣿⣻⣿
⠨⡂⠆⠕⡡⢊⠢⠨⡈⡮⡾⢜⠦⠂⡘⡰⡩⡚⡺⢝⢼⢡⢨⢺⣯⣿⣷⣿⢿⣟
⠡⡨⠨⢂⣢⠡⢊⢔⡽⡣⣋⢞⡝⢵⢲⡐⡕⡜⡄⠐⠨⡋⢔⢹⣿⡿⣷⣿⣿⣿
⠐⣼⢿⠫⡐⠌⡂⡾⢜⠜⡕⡽⡪⢏⡗⡧⣣⢣⢲⠠⡀⢜⠰⡡⠻⣿⣿⣯⣷⣿
⣸⣶⠟⡑⢄⢱⣸⣅⠅⠨⠈⠄⠌⡢⠨⢑⠑⢣⠱⡹⣪⠄⠑⢕⣯⢝⢿⣽⣻⣿
⡟⡐⡐⡐⣰⣰⣿⡍⠀⠂⠁⢌⠊⠔⡑⠄⠌⠄⡈⠪⡱⠏⣇⠕⡺⣿⣮⣛⢻⣿
⢇⢂⠢⢢⢯⣿⣿⣦⣄⠈⠐⠠⠡⢑⠠⠁⠈⠢⠨⠔⢘⢕⢵⣱⢑⢿⣿⡿⣷⣖
⢐⡐⠡⡿⣦⢿⣷⣿⠇⠀⢁⠨⠀⠅⢂⠁⠈⠀⡂⠌⢀⠎⣮⡪⡇⡆⠽⣿⣿⣿
⢘⢌⣧⠚⣿⢿⣷⣿⠂⠈⢀⠠⠐⠈⠠⠈⡀⠠⠐⢀⢁⠈⡎⠮⡺⡘⠐⠻⣾⣿
*/
int ans=20;
int p[20];
void rec(vector<int>&a, vector<int>&pos, int l, int r, int lx, int rx) {
//cout<<"! "<<l<<' '<<r<<" "<<lx<<' '<<rx<<'\n';
//for(auto&x:a) cout<<x+1<<' '; cout<<'\n';
//for(auto&x:pos) cout<<x<<' '; cout<<'\n';
//cout<<'\n';
if (r-l==1) {
int c=0;
forn(i,a.size()) c+=pos[i]!=p[i];
ans=min(ans,c);
return;
}
if (a[l]==lx) {
rec(a,pos,l+1,r,lx+1,rx); return;
}
if (a[l]==rx) {
rec(a,pos,l+1,r,lx,rx-1); return;
}
if (a[r]==lx) {
rec(a,pos,l,r-1,lx+1,rx); return;
}
if (a[r]==rx) {
rec(a,pos,l,r-1,lx,rx-1); return;
}
int x=a[l], y=a[r];
swap(a[l],a[pos[lx]]);
swap(pos[x],pos[lx]);
rec(a,pos,l+1,r,lx+1,rx);
swap(pos[x],pos[lx]);
swap(a[l],a[pos[lx]]);
swap(a[l],a[pos[rx]]);
swap(pos[x],pos[rx]);
rec(a,pos,l+1,r,lx,rx-1);
swap(pos[x],pos[rx]);
swap(a[l],a[pos[rx]]);
swap(a[r],a[pos[lx]]);
swap(pos[y],pos[lx]);
rec(a,pos,l,r-1,lx+1,rx);
swap(pos[y],pos[lx]);
swap(a[r],a[pos[lx]]);
swap(a[r],a[pos[rx]]);
swap(pos[y],pos[rx]);
rec(a,pos,l,r-1,lx,rx-1);
swap(pos[y],pos[rx]);
swap(a[r],a[pos[rx]]);
}
void solve() {
int n; cin>>n;
vii(a,n);
forn(i,n) --a[i];
vector<int> pos(n);
forn(i,n) pos[a[i]]=i;
forn(i,n) p[i]=pos[i];
rec(a,pos,0,n-1,0,n-1);
cout<<ans<<'\n';
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t=1;
//cin>>t;
while (t--) solve();
return 0;
}
Compilation message
giraffes.cpp:4:1: warning: multi-line comment [-Wcomment]
4 | // \ __ __ \
| ^
giraffes.cpp: In function 'void rec(std::vector<int>&, std::vector<int>&, int, int, int, int)':
giraffes.cpp:100:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | #define forn(i,n) for(int i=0; i<(n); ++i)
| ^
giraffes.cpp:143:9: note: in expansion of macro 'forn'
143 | forn(i,a.size()) c+=pos[i]!=p[i];
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
