oj.uz

Submission #997217

# Submission time Handle Problem Language Result Execution time Memory
997217 2024-06-11T20:50:40 Z TimDee Designated Cities (JOI19_designated_cities) C++17
100 / 100
 325 ms 82004 KB 
//             _
//   ^ ^      //
// >(O_O)<___//
//   \ __ __  \
//    \\ \\ \\\\

/*
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣿⠷⢛⠩⣡⠦⢂⢂⢂⠂⡂⢂⢐⢀⠂⠄⡂⠄⢂⢐⠠⢀⢂⢐⢀⢂⠄⡂⡂⡂⠢⠡⡂⠪⡐⢅⠪⣙⢛⡻⡻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣯⣿⣯⣿⣯⣿⣯⣿⣽⣿⣺⡫⣿⣽⣯⣿⣽⣯⣿⣽⣯⣿⣽⣯⣿⣽⣯⣿⣽⣯⣿⣽⢾⣻⣵⢞⣴⠟⡡⡊⠄⠢⢐⠨⢐⢐⢐⠠⢁⠅⡂⠌⠔⡐⡨⢐⠐⡐⡈⡢⢑⢐⢅⠪⡘⢔⠌⡪⢐⢅⠇⡎⡪⡪⣚⢮⡻⡾⣿⣾⣿⣽⣯⣿⣾⣿⣾⣿⣽⣿⣽⣯⣿⣽⣯⣿⣽⣯⣿⣽
⣿⣻⣿⣽⣿⣽⣿⣻⣿⣽⣞⢽⢽⣿⣟⣿⣿⣻⣿⣟⣿⣿⣻⣿⣟⣿⣟⣿⣻⣯⣯⣷⣿⣻⣚⣞⠵⡩⢂⠊⠌⠨⡐⠨⢂⢂⠢⠨⡐⢔⠨⡘⢌⢐⢐⠔⡡⢂⠢⠪⡨⡢⢱⠨⡊⢆⢣⢪⠢⢅⠣⡣⡣⡱⡑⡕⡯⣿⣾⢿⣾⣿⣻⣿⣯⣿⣾⣿⣯⣿⣟⣿⣟⣿⣿⣻⣿⣟⣿⣟
⣿⣿⣟⣿⣽⣿⣻⣿⣻⣿⣻⣿⣻⣯⣿⣿⣽⣿⣯⣿⣿⣽⣿⣯⣿⣿⣻⣿⢿⣻⣿⣻⣿⢻⡝⡪⡑⢌⢐⠁⠌⡂⡊⢌⢂⢂⠅⢕⠨⡂⢕⠨⡢⡑⢔⢑⢌⠆⢕⢑⢌⢪⢊⢎⢎⢎⢪⡸⡸⡱⡱⡌⡎⣞⢼⢸⢪⢮⡻⣿⣿⣾⣿⣯⣿⣿⣽⣷⣿⣟⣿⣟⣿⣿⣽⣿⣯⣿⡿⣟
⣿⣯⣿⣿⣟⣿⣟⣿⣟⣿⣟⣿⣟⡯⣿⣯⣿⣯⣿⣯⣿⣯⣿⣯⣿⣟⣿⡿⣿⡿⣟⣯⡾⢣⢑⠌⡐⡐⡐⡐⠅⡂⡪⠐⡐⠔⡅⢕⠨⢌⢢⠣⡢⡱⢡⢃⢎⠜⡨⡊⡆⢎⢪⡪⡎⣞⡜⡼⣸⠸⣜⢼⢸⢬⢳⢳⡱⡱⢕⢇⠯⣷⣿⣯⣷⣿⣟⣯⣿⣿⣻⣿⣿⣽⣿⣽⣿⣽⣿⣿
⣿⣿⣽⣾⣿⣟⣿⣿⣻⣿⣟⣿⣷⢿⣟⣿⣽⣿⣯⣿⣯⣿⣯⣿⣯⣿⣻⡿⣟⣟⣯⠷⢩⢂⢂⢊⢐⢐⠰⡈⡂⡪⠠⡑⡌⠕⡌⡢⢣⢑⢅⢇⢪⠸⡰⡱⡘⡌⡆⡣⣪⢪⢪⡪⡎⣗⢵⢝⡮⣣⡣⡫⡺⣜⢵⡓⡽⡸⡸⡱⡹⡘⢾⣽⡿⣯⣿⣿⣟⣿⣟⣿⣾⣿⣯⣿⣿⣽⣿⣷
⣿⣾⡿⣟⣷⣳⣻⣿⣻⣯⣿⣿⣻⣿⣿⢿⣟⣯⢯⢯⣿⣿⣽⣿⣻⣿⣻⣿⣿⢿⢫⢘⠔⢐⢐⢐⢐⠔⠡⢂⢒⢌⠪⡢⡑⡅⢇⢊⢆⢣⢱⢸⠸⡘⡌⣆⢳⢨⢪⢪⢪⡪⣣⢫⢞⢜⢕⢗⢝⢮⢺⡸⡜⢎⢮⢺⢜⢜⢜⢜⢜⢌⢇⢟⣿⣿⣟⣷⣿⡿⣟⣿⣿⣾⢿⣻⣾⣿⣷⣿
⣾⡿⣿⣿⣿⢿⣽⣿⣟⣿⣿⣽⣿⣽⣾⣿⣿⣿⣽⣽⣿⣽⣿⣽⣿⣟⣿⣯⠟⢕⢡⢑⠨⢐⢐⢐⠔⠡⢁⠢⡱⢰⢑⠱⡐⡕⢅⢕⢱⢱⢱⢱⠱⡱⡱⡱⡕⡕⡵⡹⣜⢸⢸⢸⢱⢕⢕⢕⢭⢳⡱⡕⣝⢜⢜⡜⡎⣎⢎⢎⢜⠜⣜⢜⢷⣿⣻⢿⣻⣿⣿⣿⣾⣿⣿⣿⡿⣿⣾⣿
⣾⣿⣿⢿⣾⣿⣿⡽⣿⣻⣽⣿⣾⣿⢿⣻⣽⣾⣻⣿⣽⣿⣯⣿⣯⣿⠽⡂⡣⢑⠐⢄⠕⠡⡐⢌⠌⢌⠢⡱⠸⡐⡅⡣⡱⡸⡐⡕⡱⡑⡅⡇⡇⡣⡣⡫⡣⣪⡎⡇⣇⢣⢱⢱⢱⢱⢑⢕⢕⢕⢕⢕⢕⢕⢕⢜⢎⢮⢢⢣⠱⡑⡜⡵⡱⡻⣿⣿⡿⣿⣾⣿⣾⣿⣾⡿⣿⣟⣿⣾
⣻⣯⣿⣿⢿⣻⣽⣿⢿⣿⢿⣻⣗⢯⡻⡻⡿⣿⣿⣻⣯⣷⣿⡷⣟⣍⣪⢴⡜⡐⢌⠢⠨⡨⠨⡐⢌⠆⡕⢜⠡⡱⠨⡢⡣⣊⢢⢱⠱⡱⡱⡱⡡⡣⡣⡣⡱⣯⢿⡜⡔⡕⡅⡇⡇⡕⡕⢕⢅⢣⢣⢣⢣⢣⢣⠣⡣⡣⡣⡣⡩⡊⢆⡻⣽⡜⣽⣷⣿⣿⣷⣿⣷⣿⣷⣿⣿⡿⣟⣿
⢯⣞⣮⣻⡻⣿⣿⢿⣿⢿⣿⣿⢗⢧⡫⡮⣻⣿⣽⣿⡿⣟⣿⣿⣻⣽⡛⢕⣨⡬⢂⢐⢑⠠⠡⡘⢔⠱⡘⠔⡑⢜⢨⠪⡒⡔⡸⡰⡱⡱⡑⡕⡌⡎⡜⡰⡽⣯⢷⢯⡪⡪⡸⡨⡪⡸⡸⡸⡸⡘⡜⡌⡎⡜⡔⡕⢕⢕⢕⠕⡌⠌⡆⢇⡻⣟⣎⢷⣿⣷⣿⣷⣿⣯⣿⣯⣷⣿⣿⣿
⢕⣗⣵⣳⢽⣟⣿⣿⡿⣿⣿⣽⣏⢗⣝⢮⣳⣿⡿⣷⣿⣿⣿⣻⣯⢗⣮⡏⡃⡂⡂⠔⡡⠈⡔⢌⠢⡑⠅⢅⠕⠅⡢⡣⠣⡊⢔⠕⡜⢜⢜⠜⡌⡎⡊⣞⣯⡯⡿⡽⣎⢎⢆⢣⢱⠸⡰⡱⡸⡐⡌⡊⡎⡆⡕⡜⢌⢎⢆⢇⢇⠕⠨⢪⢪⢻⢗⣟⣿⣯⣷⣿⣯⣿⣯⣿⡿⣟⣿⣽
⡳⡵⣳⣳⣻⣿⣻⣷⣿⣿⣿⣽⣾⣿⣾⢷⣿⣟⣿⣿⣟⣷⣿⣽⢾⢛⠣⡑⡐⡐⡐⡐⠄⡕⢌⠢⠑⢌⠊⢔⠡⢡⢃⠎⢕⢑⢸⢘⢜⠜⡔⡕⢅⠇⢮⣻⣞⣽⢽⢯⢷⢕⠥⡑⡅⢇⢕⢜⠔⡅⡣⢕⢌⠊⢎⢜⠔⢅⢇⢕⢅⢣⠡⠡⡓⣝⢽⣗⣿⣟⣿⣿⣽⣿⣯⣿⣿⣿⣿⣿
⢜⢽⡺⣿⣿⣻⣿⣟⣿⣷⣿⢿⣻⣽⣿⡿⣿⣽⣿⢷⣿⢯⣞⣪⡦⣱⢕⢐⠅⡊⠔⢀⠣⢊⢠⢂⠅⡂⡑⡐⠅⡪⡂⠪⡪⡨⠢⡣⡱⡑⡕⢜⢸⢨⢛⢚⢚⠚⠫⠫⠫⢓⢅⢇⢊⢪⠢⡱⡑⢌⢊⠔⡐⡱⡑⠜⡜⡌⢎⢪⢊⢆⠣⡑⡌⡌⡺⢜⡽⣻⢯⣿⣯⣷⡿⣿⣾⣿⣾⣿
⡸⣜⢼⢹⡫⡿⣟⣿⣿⣽⣾⣿⣿⣟⣯⣿⣿⣿⣽⣿⣯⢿⣾⢟⢅⠫⡐⢅⠪⡌⡐⠄⡃⡢⡑⠌⢊⢂⢎⠌⡢⠱⠀⢱⠨⡢⠱⡱⡘⡌⡎⢜⠰⡸⣝⢞⢜⠎⢎⢪⢸⢰⢱⡸⡨⡂⢇⢪⢘⢌⠢⠁⠈⡀⠁⠑⠨⡊⡪⡸⡐⢅⠪⢰⣱⡽⡌⣮⣮⣎⡯⣞⣷⣿⡿⣿⣿⣾⣿⣻
⡺⣪⣷⣷⣯⣮⢇⣗⢽⣿⣻⣿⡷⣿⡿⣿⡿⣾⣿⣻⣞⣟⢏⢊⡢⢱⢘⢌⢎⠆⡊⡐⡐⢌⢊⢊⠊⠌⠂⣊⡤⢥⢌⠐⢕⢌⠪⡢⢣⢱⠸⡨⠊⠊⠂⠁⠈⠈⡁⠐⢡⢳⢵⢝⡦⡣⡣⡑⡢⠪⡀⡊⢔⢌⡮⢀⢐⠸⡰⡱⡑⡰⡁⡣⣑⡻⣻⣜⡽⡿⣿⣷⣮⣗⣿⣿⣷⣿⣟⣿
⢽⣽⣻⣯⣿⣟⣮⣺⣺⢿⣻⣯⣿⡿⣿⡿⣟⣿⣾⢿⢝⢅⢧⠱⡱⡑⡕⠌⡎⠔⡐⡐⢌⠂⢅⠢⠠⠁⢰⠣⡪⡪⡨⠣⡑⢔⠱⡘⡌⢆⢣⢊⠀⡐⠠⣑⠡⣱⢸⢼⡰⡹⣮⣻⣺⢽⣎⣎⢌⠇⡎⣌⢫⠜⡊⡔⠄⢕⠨⡪⡢⠢⡱⡘⡔⣷⢹⣷⢿⣿⢿⣷⣿⡿⣷⡽⣷⣿⡿⣿
⢿⢿⣾⣞⢿⣻⣯⣿⡿⣿⣿⣿⢿⣿⢿⣟⣿⡿⡞⣍⣾⣻⣣⢗⢕⢱⢡⠑⠌⣂⠢⡨⠂⠌⠄⠌⢀⠈⢸⢨⢲⡙⠌⠌⢌⢆⢣⠱⡘⡌⡆⠕⡠⡈⠣⡙⡝⡪⡞⣏⢮⣞⣗⣗⡽⣽⣺⣗⢷⡱⡸⣘⢮⡳⡕⡕⡅⢕⢸⢸⢐⡑⠴⡑⡜⠽⣗⣿⣽⢿⣿⣟⣷⣿⣿⣿⡽⣿⡿⣿
⢿⣽⣳⡯⡯⣿⣟⣿⡿⣿⣿⣾⣿⣿⡿⣯⣿⠏⣮⣾⣳⢯⢣⢣⠣⡱⢡⠩⡊⢔⠡⠨⠨⡈⠄⡁⠠⠐⡀⠓⡜⡎⢕⢁⢂⢪⠰⠡⡣⢪⠨⡊⢜⣜⢖⣔⢦⣳⢽⣺⢽⣺⣺⢮⣻⡺⡮⡯⣗⣟⣜⢮⢎⡞⡮⡪⡂⢕⢸⠰⡐⣯⢯⢾⣼⣮⣮⢺⣿⢿⣻⣿⣟⣿⣯⣿⣟⣿⣿⣿
⢸⢹⢺⣻⢭⡻⣟⣿⡿⣿⣷⣿⢿⡾⣟⣯⢏⢮⠳⡣⢣⢪⢪⠢⡑⡕⡡⢑⢌⠢⡊⠌⡂⠂⠅⠄⡑⡐⡈⡐⠈⢝⢆⢅⢂⠂⡣⡃⡪⡂⢇⠪⡸⣪⡳⣕⡯⣺⢽⣺⢽⣳⢯⣻⢮⡫⡾⢽⡻⡺⣺⣝⡯⡯⡯⣎⢂⠪⡪⡸⢐⢿⣿⣻⣾⣯⣿⡕⣿⣿⣿⣟⣿⣟⣿⣽⣟⣯⣷⣿
⢱⢨⠢⡊⡪⡻⣯⣟⡿⣿⢷⡿⡯⡿⡳⡫⡪⡊⡎⡎⡎⡎⢆⢣⢣⠱⡈⡢⡊⡢⡑⡁⡂⠅⠅⢂⠂⡐⠐⠨⠈⠄⠃⢆⢐⠄⡱⠰⡐⢅⢣⠑⡌⡞⡮⣗⢯⣫⣗⡯⣟⡾⣽⣺⣳⡱⡡⢕⢱⢡⣷⣳⢯⡯⣯⠪⡐⡱⡱⡸⠨⣟⣿⣿⣻⣿⣻⡧⣿⣿⣾⣿⢿⣻⣿⣟⣿⣿⢿⣿
⢸⠸⡸⡨⢢⢊⢢⢑⠍⡝⢝⠞⡪⡚⡜⡜⡜⡜⡜⢜⢜⠨⡪⢸⢐⢕⢘⢌⠢⠢⡱⠐⠄⠅⡊⠄⢂⢠⡑⠈⠐⡈⢀⣆⠔⠈⢂⠇⡊⡢⡑⢅⠪⡪⡫⡾⣝⣞⡮⡯⣗⡯⣗⡯⡾⣝⡮⡧⣳⢯⢾⣺⢯⣻⡪⡁⠢⢪⠪⡊⡪⢿⣯⣿⣟⣿⣯⢿⣟⣿⣾⣿⣿⡿⣟⣿⣯⣿⣿⣿
⠰⡑⡅⡣⠣⡊⡢⢣⢑⢜⢔⢕⢕⢱⠱⡑⡕⡱⢨⢃⢆⠣⡘⡌⠆⡂⡢⡑⠌⢌⠢⡑⡁⡊⠄⠅⠢⢘⣦⡁⡂⠐⠠⢈⠣⠐⠀⠎⡪⠰⡘⡌⡪⡪⢯⡺⣵⡳⡯⡯⣗⡯⣗⡯⡯⡳⠙⠜⣘⢸⣙⣞⡽⡺⠐⡀⡣⢱⢱⢱⡪⣹⣿⣯⣿⣿⣽⣿⡿⣟⣿⣾⡿⣿⣿⡿⣟⣯⣿⣿
⠨⡢⡑⢜⢘⠜⡸⢘⢌⠆⡕⢔⡑⡔⢕⠡⡂⡊⡢⢑⠔⢅⢃⠢⢑⠐⠔⡠⢑⠄⡃⢆⠕⡨⡘⣬⠌⡂⣳⣷⠄⠅⡘⠐⡀⠂⡁⠌⡊⢎⠔⢕⢌⢪⢳⡹⣪⢞⡽⣝⢮⣻⡺⣜⣖⢮⢏⠯⡪⣺⢺⡪⠎⠠⢐⠐⡌⡪⡢⣻⣯⣒⢿⣯⣿⣾⣿⣷⣿⣿⣿⣟⡿⣿⣷⣿⣿⣿⡿⣿
⢌⢂⠪⠨⡂⠕⢌⠢⡢⡑⢜⢐⢑⢌⠢⡑⢔⠔⢜⠰⡑⡑⠄⠕⡠⠡⠑⠄⠅⡂⡪⡂⡣⣫⢷⢹⣣⡊⠔⣿⢺⣲⣄⡡⠀⠅⠠⢂⠪⡨⡊⡪⡪⡊⡆⢝⢜⢵⢝⢮⡳⡳⣝⡞⡮⡣⡣⡣⣣⡳⡝⢼⠀⢂⠂⢅⢣⢣⢹⣽⣿⢿⣞⣿⢿⣽⣾⣯⣿⣿⣾⣿⣿⢿⣽⣿⣽⣿⣻⣿
⠔⡨⠨⡨⢂⠣⡑⡑⢔⠨⠢⡑⢔⠢⠱⡘⢔⠡⠅⢕⠨⡐⢡⢑⠠⠡⠡⠡⠨⠢⡱⡱⡽⣽⢿⡷⣝⢗⢅⠫⢫⠳⡙⡪⢀⠠⢑⢀⢂⢒⠌⢆⢣⢣⢝⠰⡐⢔⠩⡑⠹⢹⢪⢞⢽⡹⣝⣞⢞⢎⢎⢽⣷⠡⡈⢔⢕⢕⢽⣷⣿⣿⣿⣽⣿⣿⢿⣻⣿⣾⣿⣾⣿⣿⡿⣿⣽⣿⣜⣮
⢈⠢⡑⠔⡡⠊⠔⡨⠠⠡⠡⠨⢐⠨⠨⡐⡐⡡⠡⡁⡢⠨⢂⠂⢌⠌⢌⠌⣜⣼⣽⣺⡝⡾⡹⡹⡸⣝⢜⢮⡲⣕⢬⠢⡂⠆⡂⡂⠢⠀⠕⡑⡌⡪⢪⢱⢡⠣⡑⡌⡊⣂⠂⠉⠘⠊⠃⠓⣡⢇⣗⢽⡗⣕⠀⡎⡎⡦⣿⢿⣷⣿⣯⣿⣿⣾⣿⣿⡿⣷⣿⣷⣿⣷⣿⣿⡿⣯⣿⣿
⠠⡑⠌⢌⠢⠑⢅⠢⠡⠡⠡⡑⠄⠅⢅⢂⠢⠨⢂⠢⢊⠌⢄⠅⠅⢌⢂⢣⡮⣷⡿⡎⡎⡞⡜⣜⢕⢗⡽⣕⢗⡕⣗⢽⡹⡵⣢⢦⢅⠅⢌⠐⢅⠇⡇⡎⡪⡪⡊⡆⢕⠔⠀⠀⠈⠌⡨⢐⠨⢙⢎⣟⣯⠇⢌⢎⢂⢻⣽⣿⢿⣷⣿⣿⣾⣿⣯⣿⣿⢿⣯⣷⣿⣯⣿⣷⣿⣿⣿⣻
⠨⠢⡑⡡⠨⡊⠔⢌⢊⠌⢌⠔⠌⢌⢂⠢⡡⡑⡐⢅⠅⡪⢐⠡⡑⢕⢨⣾⡿⡟⢟⠕⡕⢕⠝⠜⡜⣕⠧⡓⡯⡺⡵⡫⣞⣝⢮⡳⣝⣝⢔⢅⠅⢇⢇⢇⢇⢎⢪⢪⠢⡃⠀⠀⠁⠀⠂⠢⠡⡑⡰⡐⠝⢄⠕⢌⢂⢂⢳⣿⣿⡿⣷⣿⣷⣿⣯⣿⣾⣿⣿⣿⣻⣽⣿⣽⢯⣾⣿⣿
⠨⡈⡂⡪⠨⡂⠕⡁⡂⡊⢔⢬⠮⣒⣥⢷⠻⡐⠅⢕⠨⢂⠢⡣⢑⢡⣟⣿⠘⠜⡌⣆⢮⢢⡕⣗⡬⣢⣣⡣⡧⣕⢕⣍⡪⡨⡣⡫⣞⢮⡳⡕⡅⡣⢣⢣⢣⢣⢣⠪⡒⡄⠀⠁⠀⠁⡀⠈⠈⠰⡐⢜⠨⡢⢃⢅⠪⡐⠼⣿⣷⣿⣿⣿⣾⣿⣽⣿⣻⣽⣷⣟⣿⣿⣟⣿⣿⣿⣯⣿
⢐⠰⢐⠐⢥⣶⣷⣶⣾⡾⣾⡾⡝⡫⠨⠢⡑⢌⠪⢐⢈⠢⡃⠪⣐⣵⣟⠭⣊⢎⢇⢧⢳⢱⢝⢮⡺⣕⢗⡝⣞⢮⡫⣞⢵⡻⣮⣲⡡⣓⡝⣎⢧⢑⢅⢇⢇⢇⢇⢇⢕⢜⢄⢑⠈⠀⡀⠄⠀⠄⠌⡢⢱⢡⢑⠔⡑⢌⠪⡹⣿⣽⣷⣿⣷⣿⣟⣿⡿⣟⣿⣿⢿⣽⣿⢿⣽⣾⣿⣿
⠐⠌⡂⢅⢹⣯⣷⣿⣷⣿⠟⢕⢼⢐⢑⢑⠌⡐⠨⢐⠐⢅⠊⢌⣾⣟⣧⡣⡣⡱⢹⢸⢸⢜⢮⡺⡜⣞⢼⡺⣪⢞⠮⣎⢗⢝⡞⣎⢯⡳⣝⢮⡳⡥⣱⢰⢑⢕⢕⢕⢕⢌⢆⢇⠅⢅⠀⡀⠄⠀⢁⢊⠢⡑⢅⠕⡅⢕⢱⠐⡙⣿⣿⣽⣾⣿⣟⣿⣿⣿⡿⣿⣿⢿⣿⢿⣿⣟⣿⣾
⠨⠨⢂⠅⣞⣿⣻⡽⡳⣡⣳⠫⡑⡐⡡⠂⠢⠨⡈⡂⠅⢅⢊⣾⢿⢍⢇⠇⢇⢓⢕⠇⡗⢵⢱⢕⢵⢝⡜⡜⡌⡇⡏⡎⡮⡳⡹⡪⡳⣝⢮⢧⡳⣝⢮⡳⡅⡎⡜⢜⢜⢜⢌⢆⠝⡔⡡⡀⠄⢀⠀⠑⡅⢕⡐⢅⠣⡣⡱⡈⡢⢊⠻⣟⣯⣿⣟⣿⣷⣿⡿⣿⣻⣿⣯⣯⣿⡿⣟⣿
⠨⠨⢂⢊⠝⢝⣱⣵⣾⢯⣦⢊⢐⠔⠠⠡⠡⠡⢂⢊⢌⠢⣹⡷⡹⡐⡅⢕⠅⠕⠔⡑⢌⠢⡃⢕⠸⡘⢜⠑⠅⡃⠣⡑⢌⠪⡊⡣⢫⢪⢎⡇⡧⡳⡕⣝⢮⢳⡑⡅⢇⢧⢱⢪⣪⢲⣳⢸⢨⠢⡐⡀⠘⢔⠜⢌⢊⢎⢎⢆⠊⡆⡇⡻⣿⢿⣟⣿⣽⣾⣿⣿⡿⣟⣿⣟⣿⣿⣿⣿
⢈⢪⣲⣳⣳⣿⡾⣿⣾⡟⡓⡐⡐⠌⡊⠌⢌⢊⠔⣰⠢⣱⣿⣷⡑⢌⠌⡂⠁⠄⠡⠈⠄⡁⠂⡁⠅⠨⠠⢈⢐⢀⠡⡐⡐⢔⢐⠌⡐⢐⠐⢍⢊⠇⠏⡎⡮⣣⢳⡘⡌⢎⢖⠅⢗⡯⣞⢵⡪⣊⢆⠠⠀⠂⡣⡱⡘⡌⡎⡎⣮⣔⢕⢕⢎⢿⣿⡿⣿⣻⣯⣷⣿⡿⣿⣿⣻⣷⣿⣿
⢐⢽⡿⣿⣟⣯⣿⠿⢑⢐⢐⠌⡐⡡⢂⢑⢐⢐⢌⡯⡨⣾⣿⣯⣿⣆⠁⠄⠁⠌⢈⠠⠁⢀⠂⠄⠌⢌⠌⠆⠕⠌⠪⠐⠅⠃⠆⠕⡐⡐⡈⠠⢀⠈⡈⠐⠩⢊⢇⢳⢸⠨⢪⢪⠢⡫⣞⢵⡫⣞⡔⡅⡂⠀⠐⠜⡌⡪⢪⢪⢺⣿⣳⡱⡱⡕⣕⢿⣿⣿⡿⣟⣯⣮⣫⣿⣿⣻⣽⣾
⢷⣗⣟⢿⡻⢏⠅⡑⡐⠔⡐⢌⢐⢐⢐⢐⢐⠔⡘⠅⣾⣿⣯⣿⢾⣿⡆⠀⢁⠠⢀⠠⠐⡐⢈⠌⠨⠐⠈⢈⢀⠅⡢⢒⠔⡢⡂⡂⠄⠠⠈⢈⠂⡂⡂⡡⠐⢀⠐⠡⢊⠪⡢⢑⢕⢕⢽⣕⢯⢞⢮⣣⢅⠨⡀⠀⢕⢜⢸⢸⡸⣿⡿⣟⣎⢮⡪⡪⢝⢷⣿⣿⣯⣾⣿⣿⣻⣿⣿⢿
⣿⣿⢿⡯⠃⢅⢂⢂⢊⠌⡐⡐⡐⡐⡐⡐⡐⡐⡰⣵⣹⣳⣷⡩⠛⠓⠠⠈⠄⠂⠄⠂⠡⠐⠀⠐⢀⢐⠨⢂⢑⠌⡢⢑⢌⠢⡑⠕⡅⢅⠀⢂⠠⠠⢀⠂⡁⢂⠐⠠⠀⠌⢌⠢⡑⡕⡕⠵⡯⣯⣳⡳⡳⠀⢕⠅⠄⢣⠱⡱⡱⣻⣿⣿⣽⣯⣿⣮⡪⡪⡎⡿⣿⣻⣽⣾⣿⣿⣾⣿
⣿⣾⡟⡐⡡⢁⢂⠢⠂⢅⠂⡂⡂⡂⡂⣂⢆⢢⣿⡿⣿⡿⣿⣿⡄⠈⠄⠁⠌⠀⠂⠁⠐⠈⡀⠅⢂⢐⠨⡐⡐⠅⢌⠢⠢⡑⠌⢌⠌⡢⢃⠢⠨⠨⢐⠠⠂⠄⠌⡀⠡⠐⢀⠁⠊⢜⢌⠇⡏⣞⢮⣞⡝⠀⡧⣃⢇⠌⡪⡪⡪⣙⢯⣿⣷⣿⣷⣿⣻⣮⡪⡪⡪⡝⢿⡿⣟⣷⣿⣟
⣿⣻⢂⢊⠄⢅⠂⢅⠑⠄⠅⡂⡂⡂⡢⣿⡂⣾⣟⣿⣿⢿⣟⣿⠂⡈⢀⠈⡀⢈⠀⠁⢀⠁⠠⠐⡀⠂⠌⡐⡨⠨⢂⠅⠕⡨⠨⢂⠑⠄⠡⢑⠁⠅⢂⢑⠈⡈⠢⡐⡠⢈⠠⠀⠅⡕⢌⠪⡌⡲⡙⠎⠎⢠⡻⣪⢦⢑⠈⢎⢜⢔⢽⣿⢿⣾⣿⣾⣷⣿⢿⣮⢪⢪⢪⢪⢻⢻⢿⣟
⣿⢯⠐⠄⠕⡠⠑⠄⠅⢅⠕⡐⡐⠔⣽⣿⢊⣿⣟⣿⣽⣿⣟⣷⠀⠠⠀⠠⠀⠠⠀⠐⠀⠄⠁⠄⢂⠡⠑⡐⠄⠕⡠⠡⡑⠠⠡⡑⠨⠨⠐⠠⠡⠈⠄⡐⢀⠨⠂⠢⡈⡢⠨⢂⠅⡇⢌⠪⡸⡰⡘⡔⡈⡮⡺⣝⡵⡣⡃⢅⢣⢱⢸⣿⣿⡿⣷⣿⣯⣿⣿⣿⣷⣕⠧⣇⢇⢇⢇⢏
⡿⡯⡈⠪⠨⠠⠡⠡⢡⢑⠰⡐⡌⢌⣿⡿⣸⣿⡿⣿⣟⣯⣿⣿⣿⣶⣌⡠⠐⠀⠐⠈⠀⠄⠂⠐⡀⢂⠡⢐⠈⠌⡐⠡⡂⠅⠅⠂⠅⠡⢂⠐⢀⠈⠐⠀⠄⢊⠢⣁⡐⠄⠅⠅⡢⠅⢑⠱⡈⢎⠪⡊⡎⡮⣪⣪⢺⡘⡼⣅⠪⡸⡨⢿⣷⣿⣿⣯⣿⣯⣷⣿⣯⣿⣿⣵⣯⣺⢮⣪
⣏⠢⠨⡊⠌⢌⠌⠌⡂⢆⢕⢸⣷⢁⢻⡯⣺⣿⢿⣿⢿⣿⣻⣷⣿⣷⣻⣿⣶⣌⠄⠐⠀⠂⢀⠁⠄⢂⠐⡐⠨⢐⢈⠢⠨⡘⠨⡈⠌⡈⠄⡀⠄⠀⠁⢂⠀⠀⠄⠁⡘⠸⢸⢨⠊⠄⠄⠁⢊⢪⢑⠅⡇⡗⣕⢗⣳⡹⣝⢮⢆⢊⢆⢑⠻⣯⣿⣯⣿⣟⣿⣯⣿⣟⣯⣿⣟⣿⣷⣟
⠆⢅⠕⡐⡡⠡⡈⡂⠪⡐⢴⣹⣿⣧⢂⠫⣺⣿⣿⢿⣿⢿⣟⣿⣽⣿⣻⣿⡍⠁⠀⢀⠐⠀⠠⠐⠈⠄⠂⠄⠡⢂⢐⠨⢐⠨⢐⠨⠐⡀⡂⠄⠠⠀⢈⠠⠀⠠⠐⢀⠠⠀⠀⡀⠌⠢⠡⠡⡀⢐⠱⡁⢧⢇⢯⢳⠵⣝⢮⣫⢳⡢⢊⠔⠱⡨⠻⣿⣽⣿⣟⣯⣿⣿⢿⣿⣻⣿⣯⣿
⡍⡂⡢⢂⢊⠔⡐⠌⡂⡊⢾⡮⣾⣿⣷⣌⢺⣿⣻⣿⡿⣿⣿⢿⣟⣿⣟⣿⡇⠈⠀⠠⠐⠀⠂⢀⠁⢂⠁⠌⠐⡀⠂⠌⠠⠨⢐⠨⠠⢀⠐⢈⠐⠀⡀⠐⠈⢀⠀⠢⢐⠀⠅⡀⢀⠀⠈⠨⢐⠀⡘⢌⢪⡳⣹⢪⡫⣎⢧⢳⡣⡇⡕⡌⡌⠢⠨⢌⢛⣯⣿⣿⣟⣿⣿⢿⣻⣯⣿⣿
⡒⢼⣂⠢⠡⢂⠊⠔⡐⢌⢺⣷⢹⣷⣿⣿⣅⡻⣻⣯⣿⣿⢿⣿⢿⣿⣻⡟⠀⡈⠀⠂⡀⠂⠈⢀⠠⠐⠀⠌⡀⢂⢈⠈⠨⠐⡐⠠⢁⢂⠐⡀⠌⠀⠀⠈⠠⠀⠄⠨⠂⢅⢂⠐⡐⡐⡀⠀⡂⡒⠢⠢⡡⡫⡎⣗⢝⣜⣎⢧⢳⢕⣝⠮⡪⠠⢁⠑⡔⣿⣿⣯⣿⣿⣻⣿⣿⡿⣟⣿
⢌⢽⢧⠨⢊⠔⢡⡑⡐⢄⠹⣿⣧⡻⣿⣽⣷⣝⣷⣽⡻⡿⣿⢿⣿⢿⡏⠀⠄⠀⡀⢁⠠⠀⡁⠀⠄⠐⠈⠀⠄⠠⠀⠌⡀⠂⠐⠈⠄⠂⡂⠂⢄⠀⠄⠁⠠⠀⠠⠈⠄⢅⢐⠠⠐⢐⠨⠠⠀⠕⠊⠡⡂⢇⢟⢮⡳⡕⡧⣫⢺⡸⡸⣕⢕⡕⢄⠐⢌⢻⣽⣿⣽⠻⣟⣯⣷⣿⣿⣿
⢐⠌⢿⣕⢐⠸⣔⢿⣔⠄⠅⠽⣾⣷⣝⢿⣿⣻⣞⣿⢿⣿⣾⢿⣽⣟⣿⣆⠐⠀⠠⠀⠠⠀⠔⠈⢀⠁⡈⠠⠐⠀⠂⠐⠀⠅⠨⠐⠈⠠⠠⠑⠠⠂⠄⠂⠀⠀⠄⠨⠀⢕⠐⡀⠂⠀⠁⢅⠑⠄⠂⠨⢨⢊⢗⣕⢗⡝⣎⢮⢣⡣⡯⣪⢳⡱⢅⠂⡐⠝⣿⣟⣯⡣⣿⣿⣿⡿⣟⣿
⢐⠅⠕⡻⣕⠌⣻⢷⢽⢮⡨⠂⠝⣿⣽⣮⡻⡿⣿⣻⣽⣿⣽⣿⣿⣻⣿⠝⠀⠐⠀⡈⠠⢈⠐⢈⠀⠠⠀⠂⠐⠈⠀⡁⠌⠀⠅⠌⢐⠀⢂⠈⠨⠈⡀⠀⠀⠐⠀⡂⠡⢐⠠⠀⠅⡈⢀⠂⠁⠅⠂⠌⡐⢅⢇⢗⡕⡧⡳⡱⡣⡣⡳⡱⡱⡑⢅⠂⠠⢑⠐⢝⢿⣿⣿⢿⣷⣿⣿⣿
⠐⢌⠌⡢⠙⢜⢈⢿⣻⣷⣵⡡⠑⠌⢟⣿⢿⣯⣽⡻⡿⣷⣿⣷⢿⣻⣿⠀⠄⠀⠁⡀⠠⠀⠂⡀⠂⠁⠄⠁⡈⠄⠁⢀⠀⠡⠐⠈⠠⠈⠄⢂⠀⡁⠠⠀⠀⠀⠂⠠⡁⠐⠄⠨⠐⡀⠐⠠⡱⠡⡁⠌⠄⠕⢜⠸⡘⢜⠨⢌⠪⡘⢌⢌⠢⡑⠔⠈⠀⠌⢌⢐⠕⣿⣿⢿⣟⣯⣿⣿
*/
 
#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("O3")
#pragma GCC target("popcnt")

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

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;//1e18;
const ll mod = 1e9+7;//998244353;

/*
⣿⣿⣿⣻⣿⣿⣿⣿⣿⣿⢿⢂⢂⢂⢂⠔⡐⡐⢔⢔⢡⠪⣛⣿⣿⣿⣿⣿⣿⣿
⣿⡯⣿⣯⣿⣯⣿⡿⣾⢝⢑⢐⢐⠔⢔⢱⢘⢌⢆⡧⣣⡣⡳⡜⡽⣾⣿⣯⣿⣷
⣽⣿⡿⣿⢽⣾⣿⡻⡋⡂⢆⢑⢜⠸⡸⡘⡜⣜⢜⢜⢜⢜⢕⢕⠱⡽⣿⣾⣿⣽
⢵⣻⣿⣯⣳⣿⣟⡯⠪⠐⠌⡂⢅⠇⡕⢕⢱⡿⡜⡸⡰⡑⢅⢇⠣⢝⡿⣯⣿⣿
⢼⣽⢻⣿⣻⣷⡷⡩⡱⢁⠣⢘⠄⢕⠜⠜⢒⢂⢇⣎⢆⢌⡄⢕⢁⡳⣫⣟⣯⣿
⠿⣽⣿⣿⣯⠧⡗⡕⢔⢐⢈⠐⢍⠢⡃⡣⡭⣽⣺⣺⡳⣜⢮⠸⣰⣮⣻⣿⣿⢿
⠪⡸⣘⢓⢕⠕⢕⠅⠕⡐⡐⢌⢈⠔⢌⢢⡫⣞⡾⡲⡪⡯⠇⢕⢼⣿⣾⣿⣻⣿
⠨⡂⠆⠕⡡⢊⠢⠨⡈⡮⡾⢜⠦⠂⡘⡰⡩⡚⡺⢝⢼⢡⢨⢺⣯⣿⣷⣿⢿⣟
⠡⡨⠨⢂⣢⠡⢊⢔⡽⡣⣋⢞⡝⢵⢲⡐⡕⡜⡄⠐⠨⡋⢔⢹⣿⡿⣷⣿⣿⣿
⠐⣼⢿⠫⡐⠌⡂⡾⢜⠜⡕⡽⡪⢏⡗⡧⣣⢣⢲⠠⡀⢜⠰⡡⠻⣿⣿⣯⣷⣿
⣸⣶⠟⡑⢄⢱⣸⣅⠅⠨⠈⠄⠌⡢⠨⢑⠑⢣⠱⡹⣪⠄⠑⢕⣯⢝⢿⣽⣻⣿
⡟⡐⡐⡐⣰⣰⣿⡍⠀⠂⠁⢌⠊⠔⡑⠄⠌⠄⡈⠪⡱⠏⣇⠕⡺⣿⣮⣛⢻⣿
⢇⢂⠢⢢⢯⣿⣿⣦⣄⠈⠐⠠⠡⢑⠠⠁⠈⠢⠨⠔⢘⢕⢵⣱⢑⢿⣿⡿⣷⣖
⢐⡐⠡⡿⣦⢿⣷⣿⠇⠀⢁⠨⠀⠅⢂⠁⠈⠀⡂⠌⢀⠎⣮⡪⡇⡆⠽⣿⣿⣿
⢘⢌⣧⠚⣿⢿⣷⣿⠂⠈⢀⠠⠐⠈⠠⠈⡀⠠⠐⢀⢁⠈⡎⠮⡺⡘⠐⠻⣾⣿
*/

const int N=2e5+5;
vector<pi> adj[N];
vector<pi> g[N];
    
int sub[N];
int q = 0;
int to[N], into[N];;
void pre(int u, int p) {
    for(auto&e:adj[u]) {
        int v=e.f,w=e.s;
        if (v==p) {q+=w; to[u]=w; continue;}
        into[v]=w;
        pre(v,u);
        sub[u]=max(sub[u],sub[v]+w);
    }
}
pi mx = {0,0};
void find(int u, int p, int out=0) {
    if (q + max(sub[u],out) > mx.f) {
        mx = {q+max(sub[u],out),u};
    }
    multiset<int> s; s.insert(0);
    for(auto&e:adj[u]) {
        int v=e.f, w=e.s;
        if (v==p) continue;
        s.insert(-sub[v]-w);
    }
    for(auto&e:g[u]) {
        int v=e.f, w=e.s;
        if (v==p) continue;
        s.erase(s.find(-sub[v]-into[v]));
        int x = -(*s.begin());
        q+=w;
        find(v,u,max(out,x)+to[v]);
        q-=w;
        s.insert(-x);
    }
}

int ans=0;
vector<int> z;
int d[N];
void dfs(int u, int p) {
    int mx = 0;
    for(auto&e:adj[u]) {
        int v=e.f, w=e.s;
        if (v==p) {
            ans+=w; continue;
        }
        dfs(v,u);
        if (d[v]+w > mx) {
            z.pb(mx);
            mx = d[v]+w;
        } else z.pb(d[v]+w);
    }
    d[u]=mx;
}

int best = 0;
void reroot(int u, int p) {
    best=max(best,ans);
    for(auto&e:g[u]) {
        int v=e.f, w=e.s;
        if (v==p) continue;
        ans+=w;
        reroot(v,u);
        ans-=w;
    }
}

void solve() {

    int n; cin>>n;
    int sum=0;
    forn(i,n-1) {
        int u,v,x,y; cin>>u>>v>>x>>y; --u, --v;
        adj[u].pb({v,x});
        adj[v].pb({u,y});
        g[u].pb({v,x-y});
        g[v].pb({u,y-x});
        sum+=x+y;
    }
    pre(0,-1);
    find(0,-1);
    int rt=mx.s;

    dfs(rt,-1);
    reroot(rt,-1);
    z.pb(d[rt]);
    forn(i,n) z.pb(0);
    sort(rall(z));

    int q; cin>>q;
    vector<int> pr(1);
    for(auto&x:z) pr.pb(pr.back()+x);

    while (q--) {
        int x; cin>>x;
        if (x==1) cout<<sum-best<<'\n';
        else cout<<sum-ans-pr[x-1]<<'\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

designated_cities.cpp:4:1: warning: multi-line comment [-Wcomment]
    4 | //   \ __ __  \
      | ^

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 15708 KB Output is correct
2 Correct 2 ms 15908 KB Output is correct
3 Correct 2 ms 15708 KB Output is correct
4 Correct 4 ms 15708 KB Output is correct
5 Correct 3 ms 15708 KB Output is correct
6 Correct 3 ms 15708 KB Output is correct
7 Correct 3 ms 15708 KB Output is correct
8 Correct 3 ms 15708 KB Output is correct
9 Correct 2 ms 15708 KB Output is correct
10 Correct 2 ms 15708 KB Output is correct
11 Correct 2 ms 15708 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15708 KB Output is correct
2 Correct 220 ms 48680 KB Output is correct
3 Correct 298 ms 78160 KB Output is correct
4 Correct 214 ms 46120 KB Output is correct
5 Correct 239 ms 47272 KB Output is correct
6 Correct 231 ms 52136 KB Output is correct
7 Correct 257 ms 46600 KB Output is correct
8 Correct 308 ms 79696 KB Output is correct
9 Correct 275 ms 48412 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 15704 KB Output is correct
2 Correct 236 ms 46048 KB Output is correct
3 Correct 284 ms 80920 KB Output is correct
4 Correct 222 ms 47824 KB Output is correct
5 Correct 257 ms 47348 KB Output is correct
6 Correct 247 ms 52812 KB Output is correct
7 Correct 270 ms 46872 KB Output is correct
8 Correct 294 ms 68008 KB Output is correct
9 Correct 276 ms 48928 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 15708 KB Output is correct
2 Correct 2 ms 15908 KB Output is correct
3 Correct 2 ms 15708 KB Output is correct
4 Correct 4 ms 15708 KB Output is correct
5 Correct 3 ms 15708 KB Output is correct
6 Correct 3 ms 15708 KB Output is correct
7 Correct 3 ms 15708 KB Output is correct
8 Correct 3 ms 15708 KB Output is correct
9 Correct 2 ms 15708 KB Output is correct
10 Correct 2 ms 15708 KB Output is correct
11 Correct 2 ms 15708 KB Output is correct
12 Correct 3 ms 15704 KB Output is correct
13 Correct 4 ms 16220 KB Output is correct
14 Correct 4 ms 16476 KB Output is correct
15 Correct 4 ms 16220 KB Output is correct
16 Correct 4 ms 16220 KB Output is correct
17 Correct 4 ms 16220 KB Output is correct
18 Correct 4 ms 16168 KB Output is correct
19 Correct 4 ms 16220 KB Output is correct
20 Correct 4 ms 16216 KB Output is correct
21 Correct 4 ms 16220 KB Output is correct
22 Correct 4 ms 16220 KB Output is correct
23 Correct 4 ms 16220 KB Output is correct
24 Correct 4 ms 16216 KB Output is correct
25 Correct 4 ms 16476 KB Output is correct
26 Correct 4 ms 16220 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15708 KB Output is correct
2 Correct 220 ms 48680 KB Output is correct
3 Correct 298 ms 78160 KB Output is correct
4 Correct 214 ms 46120 KB Output is correct
5 Correct 239 ms 47272 KB Output is correct
6 Correct 231 ms 52136 KB Output is correct
7 Correct 257 ms 46600 KB Output is correct
8 Correct 308 ms 79696 KB Output is correct
9 Correct 275 ms 48412 KB Output is correct
10 Correct 2 ms 15704 KB Output is correct
11 Correct 236 ms 46048 KB Output is correct
12 Correct 284 ms 80920 KB Output is correct
13 Correct 222 ms 47824 KB Output is correct
14 Correct 257 ms 47348 KB Output is correct
15 Correct 247 ms 52812 KB Output is correct
16 Correct 270 ms 46872 KB Output is correct
17 Correct 294 ms 68008 KB Output is correct
18 Correct 276 ms 48928 KB Output is correct
19 Correct 2 ms 15708 KB Output is correct
20 Correct 253 ms 48644 KB Output is correct
21 Correct 301 ms 82004 KB Output is correct
22 Correct 221 ms 46556 KB Output is correct
23 Correct 211 ms 46556 KB Output is correct
24 Correct 219 ms 47032 KB Output is correct
25 Correct 227 ms 47308 KB Output is correct
26 Correct 232 ms 47436 KB Output is correct
27 Correct 234 ms 47296 KB Output is correct
28 Correct 249 ms 51532 KB Output is correct
29 Correct 220 ms 47308 KB Output is correct
30 Correct 254 ms 48696 KB Output is correct
31 Correct 251 ms 47396 KB Output is correct
32 Correct 279 ms 69716 KB Output is correct
33 Correct 279 ms 48672 KB Output is correct

Subtask #6
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 15708 KB Output is correct
2 Correct 2 ms 15908 KB Output is correct
3 Correct 2 ms 15708 KB Output is correct
4 Correct 4 ms 15708 KB Output is correct
5 Correct 3 ms 15708 KB Output is correct
6 Correct 3 ms 15708 KB Output is correct
7 Correct 3 ms 15708 KB Output is correct
8 Correct 3 ms 15708 KB Output is correct
9 Correct 2 ms 15708 KB Output is correct
10 Correct 2 ms 15708 KB Output is correct
11 Correct 2 ms 15708 KB Output is correct
12 Correct 3 ms 15708 KB Output is correct
13 Correct 220 ms 48680 KB Output is correct
14 Correct 298 ms 78160 KB Output is correct
15 Correct 214 ms 46120 KB Output is correct
16 Correct 239 ms 47272 KB Output is correct
17 Correct 231 ms 52136 KB Output is correct
18 Correct 257 ms 46600 KB Output is correct
19 Correct 308 ms 79696 KB Output is correct
20 Correct 275 ms 48412 KB Output is correct
21 Correct 2 ms 15704 KB Output is correct
22 Correct 236 ms 46048 KB Output is correct
23 Correct 284 ms 80920 KB Output is correct
24 Correct 222 ms 47824 KB Output is correct
25 Correct 257 ms 47348 KB Output is correct
26 Correct 247 ms 52812 KB Output is correct
27 Correct 270 ms 46872 KB Output is correct
28 Correct 294 ms 68008 KB Output is correct
29 Correct 276 ms 48928 KB Output is correct
30 Correct 3 ms 15704 KB Output is correct
31 Correct 4 ms 16220 KB Output is correct
32 Correct 4 ms 16476 KB Output is correct
33 Correct 4 ms 16220 KB Output is correct
34 Correct 4 ms 16220 KB Output is correct
35 Correct 4 ms 16220 KB Output is correct
36 Correct 4 ms 16168 KB Output is correct
37 Correct 4 ms 16220 KB Output is correct
38 Correct 4 ms 16216 KB Output is correct
39 Correct 4 ms 16220 KB Output is correct
40 Correct 4 ms 16220 KB Output is correct
41 Correct 4 ms 16220 KB Output is correct
42 Correct 4 ms 16216 KB Output is correct
43 Correct 4 ms 16476 KB Output is correct
44 Correct 4 ms 16220 KB Output is correct
45 Correct 2 ms 15708 KB Output is correct
46 Correct 253 ms 48644 KB Output is correct
47 Correct 301 ms 82004 KB Output is correct
48 Correct 221 ms 46556 KB Output is correct
49 Correct 211 ms 46556 KB Output is correct
50 Correct 219 ms 47032 KB Output is correct
51 Correct 227 ms 47308 KB Output is correct
52 Correct 232 ms 47436 KB Output is correct
53 Correct 234 ms 47296 KB Output is correct
54 Correct 249 ms 51532 KB Output is correct
55 Correct 220 ms 47308 KB Output is correct
56 Correct 254 ms 48696 KB Output is correct
57 Correct 251 ms 47396 KB Output is correct
58 Correct 279 ms 69716 KB Output is correct
59 Correct 279 ms 48672 KB Output is correct
60 Correct 2 ms 15708 KB Output is correct
61 Correct 251 ms 48056 KB Output is correct
62 Correct 325 ms 80464 KB Output is correct
63 Correct 216 ms 45796 KB Output is correct
64 Correct 270 ms 47336 KB Output is correct
65 Correct 249 ms 49084 KB Output is correct
66 Correct 236 ms 47064 KB Output is correct
67 Correct 250 ms 46520 KB Output is correct
68 Correct 246 ms 49464 KB Output is correct
69 Correct 248 ms 52804 KB Output is correct
70 Correct 242 ms 49336 KB Output is correct
71 Correct 246 ms 50484 KB Output is correct
72 Correct 299 ms 50476 KB Output is correct
73 Correct 307 ms 67924 KB Output is correct
74 Correct 299 ms 50320 KB Output is correct