oj.uz

Submission #1023391

# Submission time Handle Problem Language Result Execution time Memory
1023391 2024-07-14T17:35:09 Z vjudge1 Fountain (eJOI20_fountain) C++17
100 / 100
 500 ms 60540 KB 
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣤⣤⣶⣶⣶⣶⠦⠶⡶⢦⠤⠤⠤⣄⣀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣠⣠⣴⣶⣿⣿⣿⣿⣿⣿⣽⣽⣿⣿⣿⣿⣿⣭⣽⣭⣯⡭⡈⢙⣽⣶⣤⣤⣄⣀⣀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣠⣶⣟⣟⣽⣾⣿⢿⣿⡿⣿⣿⣿⣿⣿⣿⣟⠟⡻⣿⣿⣟⣟⣟⣿⡻⠿⠿⠿⠿⣍⠉⠉⠉⠙⠛⠛⠒⠒⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣠⣶⣿⣿⣿⣿⡿⣾⣿⣯⣿⣿⣿⣽⣿⣷⣽⣿⣿⡿⣿⣿⣾⢿⣿⡷⣿⣿⣿⣿⣯⣭⡅⣠⣹⣢⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⣿⡿⣿⣟⣽⣿⣿⣿⣻⣿⣟⣟⣿⣻⣿⣝⣿⣯⣿⣻⣻⣿⣿⣿⣿⡪⡻⣿⣿⣽⣿⣿⣯⣻⣿⣶⣿⣖⣓⡤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⠿⢿⣿⣟⣿⣿⣻⣿⣿⣿⠿⣿⣿⡿⣿⣿⢿⣿⡯⣿⣛⣿⣕⣿⣿⡿⣿⣿⣷⢿⡿⣻⣿⣿⣿⢿⣿⣿⡻⣿⡷⠷⠯⠦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣼⡽⠹⠩⡝⡇⡿⢻⢻⢻⡛⣿⣹⣿⣿⣿⣿⣿⣽⣿⣯⣿⣿⣿⡿⣿⣿⣿⣿⣽⡿⣿⣯⣻⣿⣿⡿⣿⣿⣿⣿⣿⣝⡍⠩⠀⢘⢄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣏⣓⣂⣀⣀⠀⣜⣀⣀⠐⠐⠓⣞⠨⣿⠿⣗⣿⣿⣻⣿⣿⣽⣿⣿⣺⣿⣿⣿⣿⣻⣿⣿⣿⣝⢿⣛⠻⣻⣿⣟⣟⣿⣿⣿⣤⣐⣒⣚⣳⡀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣿⣿⠟⠻⠽⢯⣌⣶⣿⠿⡡⢴⣾⠛⢀⣷⡉⡟⣷⢊⢘⢀⡙⣷⣾⣿⣿⣿⣿⣿⣿⢿⣿⢿⣿⡿⣿⣿⣽⢋⣝⣿⡿⣿⢿⢿⣛⢿⣿⣗⢇⠟⢦⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢾⣿⣿⣉⣉⣉⣸⣿⣿⣉⣉⢉⣿⠷⠶⠀⢸⣿⣿⢿⠀⠀⠀⠀⢸⠀⢀⡷⣿⣿⣿⢿⡿⡇⣿⣉⢾⣿⣿⠰⢶⡶⣿⣿⣿⣿⣹⣿⡀⠹⣿⣿⡹⣉⢷⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣾⣿⡭⣥⣿⣾⣿⣿⣿⣿⣿⣿⣓⡃⠐⠀⣘⣯⣿⣚⣟⢒⣓⣒⣿⣒⢺⣟⣻⡧⡉⣿⡿⠍⡭⢭⠨⠹⢿⣝⢒⡞⠀⡖⣚⢷⣙⢛⣯⣦⠈⠻⢿⣿⣮⣧⡀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣿⣿⢩⣿⣿⣿⣾⣷⣿⣿⣿⣟⠒⠀⠐⠀⠉⡿⡟⠉⠹⣿⣟⣳⣶⣆⣴⠑⠀⢳⡄⠈⣷⡁⠁⠈⠀⢈⠙⣷⠀⣀⣀⣀⠀⢨⣷⠀⠊⣟⢣⠀⠀⠉⠛⠿⣿⣄⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣸⣿⣗⡺⣿⣿⣿⣿⣿⣿⣿⡿⡏⠍⠁⢈⠀⠉⠁⣷⠩⠩⠨⢿⣷⣿⣿⡟⠀⠈⠅⠽⣹⣯⡵⣖⣶⣶⣶⡖⣿⡬⢭⡭⣽⣿⠭⣿⡠⠥⣼⣷⢧⠀⠀⠀⠀⠀⠙⠳⢄⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣟⣿⡏⡃⢀⣠⣬⣶⣶⣦⣍⢀⠈⢸⣘⣧⣿⣿⣏⠀⣀⠀⣃⣷⢿⣼⣽⣆⡲⡦⢵⣾⣿⠃⣧⣿⣿⡼⣿⣿⣇⣻⣿⣘⡆⠀⠀⠀⠀⠀⠀⠈⠛
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢦⣾⠟⠻⠹⢰⣶⣆⡚⢷⡀⠠⠶⡞⣾⣿⠤⠀⠠⡀⢒⡞⠻⣷⠐⢻⣿⣮⡕⣷⣿⡖⣿⣿⣿⡏⣽⣿⣿⢶⣿⣿⢾⡄⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣿⣽⣿⣿⡯⡿⢿⢽⣽⣮⣯⣯⡟⠬⠅⢡⡀⣠⣽⣿⣧⠵⠁⠀⠀⠇⡍⢿⠀⠀⠤⠀⠏⠩⠬⠹⡤⠀⣿⢝⡿⡯⣾⣯⣿⣟⣯⣖⣺⣿⣕⠽⣯⣿⣬⣽⡀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣾⣿⣻⣿⣿⠷⠿⠿⣻⣿⣟⣿⣿⠆⠁⢠⣿⣿⡽⠿⡿⣿⠀⠀⠀⠀⠀⠉⠋⠀⠀⠀⠀⠒⠉⠊⢈⠋⠁⡋⣻⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⣷⣿⣿⣟⣹⣿⡆⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣾⣿⡿⣿⣿⣿⣿⡭⢹⣿⣿⣻⣽⣿⡀⠀⢨⡇⠉⠍⢌⠼⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠴⣶⢶⠾⢦⣆⠂⠚⣿⣷⣽⡗⣿⡯⣿⠵⢿⣯⣯⣿⣿⣿⣕⣯⣇⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⣯⣿⣗⣿⣿⣿⡓⣒⣛⣽⣿⣿⢿⣯⠥⠀⠈⢶⡂⠐⣾⠆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠉⢙⣿⣌⣮⠽⣿⣍⢯⣻⣻⣯⠭⠥⣯⠬⣿⣿⣿⣟⣿⣻⣾⣏⢹⡀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⣿⣾⣿⣷⣿⣿⡇⡇⠴⣹⣿⣿⣾⣉⢹⣄⡀⠀⠀⠉⠉⠀⠀⠀⠀⠀⠀⣠⡄⠀⠀⠀⠀⣀⣷⣶⣾⣿⣿⠈⠀⡉⣿⢙⣏⢾⣏⡉⡁⡁⣹⣿⣿⣳⣷⣿⣿⢞⣾⡌⡇⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣿⣯⣿⣿⣿⣿⣭⠭⢭⣿⣿⣷⡒⢀⡶⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⡿⠇⠀⠀⠀⠰⡟⣿⢨⠽⢕⡟⠀⠂⣲⡟⠒⢺⣽⣷⣾⡶⠒⣺⣿⣯⣿⣿⣾⢽⣝⣿⠆⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣸⣿⣿⣿⣿⣟⣿⣿⣿⣧⣚⣾⣚⣿⣿⠬⠤⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠋⠀⠀⠀⠀⠐⣇⠈⢐⢰⡏⠁⠠⢠⡿⠤⣤⣿⣻⣟⣿⠥⣾⣿⣿⣿⣿⣿⣿⡾⡳⣿⡇⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⡷⣿⣿⣿⣿⡿⣽⣿⢿⣿⣿⠶⠾⣿⣿⢉⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠒⠒⠛⠀⠤⠾⣛⣀⣽⣿⣿⣿⣿⣿⡿⣿⣿⣿⣿⣿⣿⣿⣿⣮⣿⡇⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⣯⣿⣿⣿⣿⣫⣫⣿⣿⢕⣿⣭⢹⡿⣿⣷⣐⣀⠂⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠐⣢⣫⣿⣿⣟⣿⣿⣾⣻⣿⣿⣿⣿⣿⣿⣿⣿⣷⢿⡇⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⣿⣿⣿⣿⣿⣿⢟⢟⣿⣿⣷⡿⣟⢄⣻⡻⣿⣷⡬⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣾⣛⣿⣿⡿⣿⣿⣟⢟⣟⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⡄⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⡿⣿⣿⣿⡗⣽⣿⣿⣿⣿⣕⡽⣍⢯⣿⣿⣿⢅⠠⠀⠀⠀⠀⠉⠙⠂⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣬⣿⣿⣿⣿⣿⣿⣯⢿⣿⣿⡵⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡽⣄⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⡀⠀⠀⠀⠀⢸⣿⣿⠇⢸⣿⣿⣯⣺⣿⣿⣿⣿⣿⣿⣦⢟⣿⣯⣿⣿⣷⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣼⣾⣿⣿⣿⣿⣿⣿⣗⣟⣿⣿⣺⡯⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣺⡆⠀⠀⠀⠀
⠀⠀⠀⠀⢀⣤⣶⣾⣷⣿⣿⣯⣳⡤⣀⣿⡏⠀⢸⣿⣿⣿⣾⠯⣿⣿⣿⣿⣿⣿⣿⢷⣿⣩⠨⠽⡿⣷⣄⠀⠀⠀⠀⠀⠀⠀⣀⣀⣠⣤⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣿⣿⢏⣀⣻⣿⣿⣿⣿⣿⣿⣿⣾⡿⣿⣯⢿⡀⠀⠀⠀
⠀⢀⣠⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣟⣖⢤⣘⣿⣿⣿⣷⣽⣿⣿⣿⣿⣿⣿⣷⣗⣭⡿⣬⣭⡯⣭⣿⣿⣿⣿⣿⣽⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣺⣿⣿⣿⣕⢒⣿⣿⣿⣿⣿⣿⣿⣿⣻⣾⡿⣿⣿⣇⠀⠀⠀
⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣝⢻⡻⣿⣟⣿⢟⡿⣿⣾⣿⣷⣟⢶⠐⢐⣰⣇⣲⣗⣾⢐⣐⣸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢽⣟⢽⣿⡺⢩⣿⣿⣿⣿⣿⣿⣿⣿⣿⣟⡯⡾⣿⢽⡄⠀⠀
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣾⣾⡻⣷⣿⣟⢿⣿⣿⣿⣿⢷⡤⠀⠴⠑⠷⠶⠰⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⣻⢿⣿⣿⣿⣿⣿⣿⣿⣻⣿⣯⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣿⢟⢟⢿⣿⠀⠀
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣝⣿⣿⣝⣿⣿⣿⣿⣷⣽⣄⠄⠀⠄⠀⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢝⣿⡆⠙⠿⣿⣿⣿⣿⣺⣺⠟⢰⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣗⣟⢽⠈⢿⡆⠀
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⢾⣿⣿⣿⣿⣿⣾⣇⡀⠆⢀⣿⣿⣷⣿⣿⣿⣿⢿⣿⠁⠈⣿⣿⣿⢾⡇⠀⠀⠀⠹⣿⡿⣿⣉⣈⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢏⣏⢾⠀⠀⣇⠀
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣗⣿⣿⣿⣿⣿⣿⣮⡶⣤⣿⣿⣿⣿⣿⣿⣿⡿⣿⡗⠀⠀⠀⠙⢿⣿⣻⠀⠀⠀⠀⠈⣿⡿⣶⣾⣽⣿⡿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣿⡏⠀⠀⣼⠀
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢽⣿⣿⣿⣿⣿⣿⣿⢿⣿⣿⣿⣵⢝⢵⣿⡯⣯⠃⠀⠀⠀⠀⠀⠙⢿⡄⠀⠀⠀⢰⣿⠗⠉⠙⠿⣮⣧⡈⠻⣿⣿⣿⣿⣿⣿⣿⡯⣮⡇⠀⠀⠀⠀
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣫⣿⣿⣿⣿⣷⣿⣿⣿⣾⣾⣻⣻⣿⣻⣟⢿⣶⣄⡀⠀⠀⠀⠀⠀⠓⠀⠀⢠⡿⠁⠀⠀⠀⠀⠈⠙⠻⢦⠈⠿⣿⣿⣿⣿⣿⣟⣿⠁⠀⠀⠀⠀
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣿⣾⣾⣿⣿⣿⣿⣾⣿⣿⣷⣽⣾⡿⣷⣤⣀⠀⠀⠀⠀⠀⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠓⠀⠈⠻⣿⣿⣿⣷⡏⠀⠀⠀⠀⠀
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣽⣿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣿⡿⣿⣷⣆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⢿⣿⡟⠀⠀⠀⠀⠀⠀
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⡿⣻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣾⣾⡿⣷⣆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢿⠃⠀⠀⠀⠀⠀⠀
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢯⣿⣯⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣮⣯⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠋⠀⠀⠀⠀⠀⠀⠀
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣟⣽⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡷⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣽⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣟⣿⠋⠀
*/
// skibidi rizz
#include<bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie()
#define ll long long
#define ull unsigned long long
#define pb push_back
// #define endl "\n"
#define int ll
#define F first     
#define S second
#define db double 
#define ld long double
#define short unsigned short
#define pii pair<int,int>
using namespace std;
const   ll inf = 1e18,MOD=1e9+7,N=5e5+10,MN=1e9+7,lim=1e6;
const long db Phi=acos(-1);
ll binpow(int a,int p);
struct res
{
  int d,c;
};
int t[N*4];
vector<int>g[N];
int n,q;
void build(int x,int lx,int rx){
  if(lx==rx){
    t[x]=inf;
    return ;
  }
  int m=(lx+rx)/2;
  build(2*x,lx,m);
  build(2*x+1,m+1,rx);
  t[x]=min(t[x*2],t[x*2+1]);
  // cout<<t[x]<<endl;
}
void sett(int i,int v,int x,int lx,int rx){
  if(lx==rx){
    // cout<<lx<<" "<<rx<<endl;
    t[x]=v;
    return ;
  }
  int m=(lx+rx)/2;
  if(i<=m) sett(i,v,x*2,lx,m);
  else sett(i,v,x*2+1,m+1,rx);
  t[x]=min(t[x*2],t[x*2+1]);
}
int get(int l,int r,int x,int lx,int rx){
  if(l<=lx&&rx<=r){
    // cout<<lx<<" "<<rx<<" "<<t[x]<<" "<<x<<endl;
    return t[x];
  } 
  if(rx<l||r<lx) return inf;
  int m=(lx+rx)/2;
  return min(get(l,r,x*2,lx,m),get(l,r,x*2+1,m+1,rx));
}
int lg=20;
int up[N][21];
vector<int>pref(N,0);
vector<res>fon(N);

void dfs(int v,int p=n+1){
  // cout<<v<<" ";
  up[v][0]=p;
  // cout<<p<<" ";
  pref[v]=pref[up[v][0]]+fon[v].c;
  // cout<<pref[v]<<endl;
  for(int i=1;i<=lg;i++){
    up[v][i]=up[up[v][i-1]][i-1];
    // cout<<up[v][i]<<" ";
  }
  // cout<<endl;
  for(auto to:g[v]){
    dfs(to,v);
  }
}
int getans(int R,int V){
  int initial=R;
  for(int i=lg;i>=0;i--){
    // cout<<initial<<" "<<up[R][i]<<" "<<pref[initial]-pref[up[R][i]]<<endl;
    if(pref[initial]-pref[up[up[R][i]][0]]<V){
      R=up[R][i];
    }
  }
  if(pref[initial]-pref[up[initial][0]]>=V){
    return R;
  }
  return up[R][0];
}
void solve(){
  // int n,q;
  cin>>n>>q;
  
  vector<int>con;
  for(int i=1;i<=n;i++){
    cin>>fon[i].d>>fon[i].c;
    con.pb(fon[i].d);
  }
  sort(con.begin(),con.end());
  con.erase(unique(con.begin(),con.end()),con.end());
  for(int i=1;i<=n;i++){
    fon[i].d=lower_bound(con.begin(),con.end(),fon[i].d)-con.begin()+1;
  }
  build(1,1,N);
  fon.pb({n+1,0});
  sett(n+1,n+1,1,1,N);
  for(int i=n;i>0;i--){
    int down=get(fon[i].d+1,n+1,1,1,N);
    g[down].pb(i);
    sett(fon[i].d,i,1,1,N);
  }
  dfs(n+1,n+1);
  while(q--){
    int R,V;
    cin>>R>>V;
    int ans=getans(R,V);
    if(ans==n+1){
      cout<<0<<endl;
    }
    else cout<<ans<<endl;
  }
}     
signed main() {
    IOS;
    srand(time(NULL));
    //freopen("coins.in", "r", stdin);
    //freopen("coins.out", "w", stdout);
    int UwU=1;
    // cin>>UwU;
    for(int i=1;i<=UwU;i++) { 
      // cout<<"Case alk"<<i<<": ";
        solve();
      // cout<<endl;
    }
}
ll binpow(int a,int p){if(p==0)return 1;if(p%2){return ((binpow(a,p-1)*a)%MOD);}int res=binpow(a,p/2)%MOD; return (res*res)%MOD;}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 42588 KB Output is correct
2 Correct 10 ms 42584 KB Output is correct
3 Correct 11 ms 43612 KB Output is correct
4 Correct 11 ms 44000 KB Output is correct
5 Correct 15 ms 43352 KB Output is correct
6 Correct 13 ms 42588 KB Output is correct
7 Correct 14 ms 44376 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 60312 KB Output is correct
2 Correct 328 ms 57488 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 42588 KB Output is correct
2 Correct 10 ms 42584 KB Output is correct
3 Correct 11 ms 43612 KB Output is correct
4 Correct 11 ms 44000 KB Output is correct
5 Correct 15 ms 43352 KB Output is correct
6 Correct 13 ms 42588 KB Output is correct
7 Correct 14 ms 44376 KB Output is correct
8 Correct 312 ms 60312 KB Output is correct
9 Correct 328 ms 57488 KB Output is correct
10 Correct 13 ms 44380 KB Output is correct
11 Correct 193 ms 48360 KB Output is correct
12 Correct 458 ms 60540 KB Output is correct
13 Correct 500 ms 57928 KB Output is correct
14 Correct 386 ms 55772 KB Output is correct
15 Correct 354 ms 54592 KB Output is correct