This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/**
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣤⡤⠤⣤⣄⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡴⠛⠉⠀⠀⠀⠀⠈⠙⢷⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⠟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣰⠶⣄⡀⠀⠀⠀⢠⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⡏⠀⠀⠉⠛⠶⣤⣸⡇⠀⠀⠀⠀⣀⣤⣶⣶⠒⠒⠒⠶⣬⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣤⠴⠶⣿⠀⠀⠀⠀⠀⠀⠈⠉⠉⠛⠒⠶⢿⣭⣀⡀⢻⡀⠀⠀⢠⡿⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣤⠶⠛⠋⠁⠀⠀⢸⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠉⠛⠷⣴⣞⠛⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⡴⠞⠉⠀⠀⠀⠀⠀⠀⢰⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠛⢦⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⠞⠋⠀⠀⠀⠀⢀⡤⠠⡄⠀⢰⡏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠿⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⡞⠁⠀⠀⠀⠀⣠⠖⠋⠀⣸⠇⠀⢸⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠀⢀⡀⠀⠀⠀⠀⠀⠀⢦⡀⠀⠀⠀⠸⣷⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡼⠋⠀⠀⠀⠀⢀⣴⠋⢀⢀⡴⠋⠀⢀⣼⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣽⠀⣼⢿⡄⠀⠀⠀⠀⣆⠀⠉⢦⡀⠀⠀⠀⠘⢧⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⡟⠁⠀⠀⠀⠀⣠⠟⠇⠀⠈⠉⠁⠀⣀⣾⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡟⢰⠏⠀⠻⣄⠀⠀⠀⠹⣄⣰⠟⠁⠀⠀⠀⠀⠀⢻⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⡟⠀⢀⣀⡖⠀⣰⠏⠀⠀⠀⠀⠀⢀⣼⣿⠋⠸⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣧⡟⠀⠀⠀⠹⣦⠀⠀⠀⠀⠁⠀⣶⠀⠀⣴⠛⢧⠀⢻⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⣠⠞⣩⡟⠀⠀⠈⠉⠀⢀⡟⠀⠀⢀⣀⣠⣤⣾⡿⠗⠒⠚⣿⠠⣤⠀⠀⠀⠀⠀⠀⠀⢸⣿⠓⠒⠲⠶⠶⠾⢷⣤⣀⣀⠀⠀⠙⣧⠀⠹⣆⣼⠃⠀⢷⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⡴⠟⢁⡼⣿⠁⠀⠀⠀⠀⠀⢸⠃⠀⠀⠈⠉⢠⡾⠋⠀⠀⠀⠀⠸⣆⠙⣧⡀⠀⠀⠀⠀⠀⢸⡇⠀⠀⠀⠀⠀⠀⠀⠻⣆⠉⠁⠀⠀⢹⡄⠀⠈⠁⠀⠀⠘⣷⢦⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⣠⡶⠋⢀⡴⠋⢰⡏⠀⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⣠⠟⠀⠀⠀⠀⠀⠀⠀⢻⡄⢸⣷⣄⠀⠀⠀⠀⢸⡇⠀⠀⠀⠀⠀⠀⠀⠀⠈⢳⣄⠀⠀⠸⣧⠀⠀⠀⠀⠀⠀⢿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⢰⣾⡥⠴⠞⠋⠀⠀⣼⠀⠀⠀⠀⠀⠀⠀⣸⠀⠀⠀⣰⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⢻⡄⣷⠙⠷⣄⡀⠀⢸⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢷⣄⠀⣿⠀⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⣿⡆⠀⠀⠀⠀⠀⠀⢸⡄⠀⣼⢏⣀⣤⣶⣦⣤⣶⣶⣶⣶⣶⣿⣿⣾⡆⠀⠈⠻⢦⣼⡇⢰⣶⣶⣶⣶⣶⣶⣶⣤⣤⣤⣦⠙⢧⣿⠀⠀⠀⠀⠀⠀⢸⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⣿⡇⠀⠀⠀⠀⠀⠀⠘⣇⣼⠏⠘⣿⡿⢿⣿⣿⣿⣿⣿⡏⠉⠉⠉⠙⠃⠀⠀⠀⠀⠉⠁⠘⠛⢻⣿⣿⣿⣿⣿⣟⠛⢛⠷⠀⠀⣿⠀⠀⠀⠀⠀⠀⢸⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⡟⣷⠀⠀⠀⠀⠀⠀⠀⢻⡏⠀⠀⠀⠀⣸⣿⣿⣿⣿⣿⣷⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣾⣿⣿⣿⣿⣿⡇⠀⠀⠀⠀⢰⡏⠀⠀⠀⠀⠀⠀⣾⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⣷⢹⣆⠀⠀⠀⠀⠀⠀⠈⣷⠀⠀⠀⠀⢹⣿⣿⣿⣿⣿⣿⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⣿⡇⠀⠀⠀⠀⣾⠀⠀⠀⠀⠀⠀⢰⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⢿⠘⣿⣆⠀⠀⠀⠀⠀⠐⠘⣧⠀⠀⠀⠘⢿⣿⣿⣿⣿⠏⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣿⣿⣿⡿⠃⠀⠀⠀⣼⠃⠀⠀⠀⠀⠀⣰⠟⠐⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠸⣇⣿⠙⣧⣄⠀⠀⠀⠀⠀⠘⢧⡀⠀⠀⠈⢹⠿⢟⡋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢻⡿⠀⡀⠀⠀⣼⠃⠀⠀⠀⠀⣀⡾⠋⠀⣴⣷⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⢻⣿⠀⣿⠝⠳⣤⣀⡀⠀⠀⠈⢷⣤⠇⢠⡞⠠⠾⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⠟⠁⡾⠃⣠⡾⠃⠀⠀⣀⣤⠾⠋⠀⠀⠀⡿⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣿⣸⣿⠀⠀⠀⠉⠙⠓⡶⠦⠤⣿⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠓⢰⡿⠤⠴⠶⣿⠉⠀⠀⠀⠀⠀⢠⡇⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣿⢻⠀⠀⠀⠀⠀⠃⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢲⣄⠀⠀⠀⠀⠀⠀⠀⢀⣴⠆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡟⠀⠀⠀⠀⠀⠀⢸⡇⣸⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⡿⢸⡇⠀⠀⠀⠀⠀⢿⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠛⠲⠤⣤⠤⠴⠞⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⡏⠀⠀⠀⠀⠀⠀⢸⠇⠈⣇⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣸⡇⢸⡇⠀⠀⠀⠀⠀⢸⣿⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢿⡇⠀⠀⠀⠀⠀⠀⢺⢀⠀⢿⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣸⢷⠛⣇⠀⠀⠀⠀⠀⠈⣿⠉⠻⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⣅⣸⠀⠀⠀⠀⠀⠀⢀⣿⢸⡀⢸⡇⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡿⠘⣀⣿⠀⠀⠀⠀⠀⢷⢸⡄⠀⠈⠙⠶⣤⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣠⡴⠟⠁⠀⠈⣿⠀⠀⠀⠀⠀⠀⠈⡟⣼⡇⠀⣧⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⡇⠀⢿⢿⠀⠀⠀⠀⠀⠀⠈⣧⠀⠀⠀⠀⠀⠉⠛⠶⢤⣤⣀⣀⠀⣀⡀⠀⠀⠀⠀⠀⢀⣠⡴⠞⠋⠁⠀⠀⠀⠀⢀⡏⠀⠀⠀⠀⠀⠀⢠⡇⢹⣤⠀⢹⡄⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⠀⠀⡿⢸⡆⠀⠀⠀⠀⠀⠀⢻⡆⠀⠀⠀⠀⠀⠀⠀⠀⣿⡿⠟⠋⠉⠁⠀⠀⠀⠀⠀⢸⠁⠀⠀⠀⠀⠀⠀⠀⠀⢸⠇⠀⠀⠀⠀⠀⠀⢸⡇⠈⣟⠀⠈⣷⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⢰⡟⠀⢰⡇⠘⡇⠀⠀⠀⠀⠀⠘⠀⣷⠀⠀⠀⠀⠀⠀⠀⠀⣿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⡿⠆⠀⠀⠀⠀⠀⠀⣼⠁⠀⢻⡀⠀⠸⣇⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⣼⠁⠀⣼⠁⠀⣿⠀⠀⠀⠀⠀⠀⠀⠻⣇⣀⠀⠀⠀⠀⠀⠀⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⡀⠀⠀⠀⠀⠀⠀⠀⣰⡇⠀⠀⠀⠀⠀⠀⠀⣿⡆⠀⠈⣷⡀⠀⢻⡄⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⢰⡇⠀⢀⡏⠀⠀⢻⠀⠀⠀⠀⠀⠀⠀⠀⢻⣦⣄⠀⠀⠀⠀⣠⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣧⠀⠀⠀⠀⠀⣠⣾⣿⠀⠀⠀⠀⠀⠀⢠⣠⡇⡇⠀⠀⠸⣯⡀⠀⢷⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⡾⠀⠀⣼⠁⠀⠀⠸⡇⠀⠀⠀⠀⠀⠀⠀⠀⢿⣽⡧⠴⢶⣿⣿⠖⠒⠛⠛⠃⠀⠀⠀⠚⠋⠉⠉⠉⠙⠓⠲⢾⡛⠻⣽⠃⠀⠀⠀⠀⠀⠀⢸⣿⣃⠀⠀⠀⠀⢹⣷⠀⠘⣧⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⣸⠃⠀⢸⡏⠀⠀⠀⢀⣿⠀⠀⠀⠀⢀⣀⠀⠈⠈⢷⠖⠚⠋⠁⢹⡇⠀⢀⣴⠶⠶⢦⣄⣀⣤⡶⠶⠤⠤⠤⠶⠾⠇⢰⡏⠀⠀⠀⠀⠀⠀⠻⣿⣿⣤⡀⠀⠀⠀⠀⢿⣀⠀⠸⣆⠀⠀⠀
⠀⠀⠀⠀⠀⢰⠏⠀⢀⡿⠀⠀⠀⣰⠟⢹⣿⡄⠀⠀⠀⠻⣄⠀⠀⠘⣷⣤⣄⣀⣈⡙⠛⢹⡷⢶⣦⣴⣾⣛⣻⢯⣴⣦⠴⠖⠃⠀⢀⡾⠀⠀⠀⠀⠀⠀⠀⢰⣿⡇⠀⠹⣆⠀⠀⠸⡞⣧⣆⠀⠹⣄⠀⠀
⠀⠀⠀⠀⢠⡟⠀⠀⡼⠁⠀⠀⣰⠏⠀⠈⣟⣧⠀⠀⠀⠀⢻⣆⠀⠀⠈⣧⡿⠀⠈⠉⠛⠛⣻⣿⡿⢿⣿⡍⠉⠀⠀⠀⠀⠀⠀⠀⡾⠁⠀⠀⠀⢀⣴⠀⠀⡾⣿⠁⠀⠀⠘⣧⠀⠀⢿⠘⣟⠀⠀⢻⡄⠀
⠀⠀⢀⣠⡟⠀⢀⡾⠃⠀⠀⣰⡏⠀⠀⠀⣻⠘⣧⠀⠀⠀⠀⢻⣷⡄⠀⠘⢷⡀⠀⠀⠀⠀⠩⣉⠁⠈⣛⡁⠀⠀⠀⠀⠀⠀⣀⣾⠁⠀⠀⣀⣠⣟⠁⠀⣠⣤⡟⠀⠀⠀⠀⠘⣧⡄⠘⡇⠙⣇⠀⠀⠻
*/
#include <bits/stdc++.h>
using namespace std;
#define i64 long long
#define ld long double
#define bit(n,i) ((n>>i)&1)
#define pii pair<int,int>
#define sz(x) (int)x.size()
#define FOR(i,a,b) for(int i=a; i<=b; i++)
#define FOD(i,a,b) for(int i=a; i>=b; i--)
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(),x.end()
#define __sumairu__ main()
#define die_hard_onimai_fan void seggs()
#define file(name) if(fopen(name".inp","r")){freopen(name".inp","r",stdin);freopen(name".out","w",stdout);}
#define brute(name) if(fopen(name".inp","r")){freopen(name".inp","r",stdin);freopen(name".ans","w",stdout);}
#define TIME (1.0*clock()/CLOCKS_PER_SEC)
#define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ai(n) array<int,n>
#define dbg(x) {cerr<<#x<<' '<<x<<endl;}
#define dbgArr(arr,n) {cerr<<#arr;FOR(_i,1,n)cerr<<' '<<(arr)[_i];cerr<<endl;}
template <typename T,typename U>
ostream& operator<<(ostream &os,pair<T,U>p){
return os<<"{"<<p.fi<<", "<<p.se<<"}";
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
i64 Rand(i64 l,i64 r)
{
i64 ans=l+1ll*rd()*rd()%(r-l+1);
assert(l<=ans&&ans<=r);
return ans;
}
//const i64 base=1e9+7;
//const i64 mod=(1ll<<53)+5;
#define i64 long long
#define debug 0
//const int mod=1e9+7;
//const int mod=998244353;
const int inf=1e9;
///check the limits, dummy
const int N=1e5+5;
struct node
{
int l,r,id;
}a[N];
int n,q;
int id[N];
int f[20][N],up[20][N];
int get(int l,int r)
{
if(a[l].l<=a[r].l)return l;
return r;
}
int query(int l,int r)
{
int k=31-__builtin_clz(r-l+1);
return get(f[k][l],f[k][r-(1<<k)+1]);
}
die_hard_onimai_fan
{
cin>>n>>q;
FOR(i,1,n)
{
cin>>a[i].l>>a[i].r;
a[i].id=i;
}
sort(a+1,a+n+1,[&](auto x,auto y){
if(x.r!=y.r)return x.r<y.r;
return x.l<y.l;
});
FOR(i,1,n)
{
id[a[i].id]=i;
f[0][i]=i;
}
for(int j=1; (1<<j)<=n; j++)
{
for(int i=1; i+(1<<j)-1<=n; i++)
{
f[j][i]=get(f[j-1][i],f[j-1][i+(1<<j-1)]);
}
}
FOR(i,1,n)
{
int l=1,r=i;
while(l<r)
{
int mid=(l+r)/2;
if(a[mid].r>=a[i].l)r=mid;
else l=mid+1;
}
if(l!=i)up[0][i]=query(l,i-1);
}
FOR(j,1,19)
{
FOR(i,1,n)up[j][i]=up[j-1][up[j-1][i]];
}
while(q--)
{
int s,t;
cin>>s>>t;
s=id[s],t=id[t];
if(s==t)
{
cout<<0<<'\n';
continue;
}
if(a[s].r>a[t].r)
{
cout<<"impossible\n";
continue;
}
if(a[t].l<=a[s].r)
{
cout<<1<<'\n';
continue;
}
int ans=0;
FOD(i,19,0)if(a[up[i][t]].l>a[s].r)
{
t=up[i][t];
ans+=(1<<i);
}
if(up[0][t]==0)
{
cout<<"impossible\n";
continue;
}
cout<<ans+2<<'\n';
}
}
__sumairu__
{
FAST
file("");
int tt=1;//cin>>tt;
while(tt--)seggs();
cerr<<"\nTime elapsed: "<<TIME<<" s.\n";
}
/**
8 1
1 2
3 4
1 5
6 7
5 10
10 20
15 20
999999999 1000000000
1 7
*/
Compilation message (stderr)
events.cpp: In function 'void seggs()':
events.cpp:132:49: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
132 | f[j][i]=get(f[j-1][i],f[j-1][i+(1<<j-1)]);
| ~^~
events.cpp: At global scope:
events.cpp:57:21: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
57 | #define __sumairu__ main()
| ^~~~
events.cpp:189:1: note: in expansion of macro '__sumairu__'
189 | __sumairu__
| ^~~~~~~~~~~
events.cpp: In function 'int main()':
events.cpp:59:53: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
59 | #define file(name) if(fopen(name".inp","r")){freopen(name".inp","r",stdin);freopen(name".out","w",stdout);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
events.cpp:192:5: note: in expansion of macro 'file'
192 | file("");
| ^~~~
events.cpp:59:83: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
59 | #define file(name) if(fopen(name".inp","r")){freopen(name".inp","r",stdin);freopen(name".out","w",stdout);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
events.cpp:192:5: note: in expansion of macro 'file'
192 | file("");
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |