제출 #997115

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
997115		TimDee	Port Facility (JOI17_port_facility)	C++17	0 / 100	1 ms	344 KiB

port_facility

//             _
//   ^ ^      //
// >(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;

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

struct sgt {
    vector<int> a,t; int sz=1;
    sgt(int n) {
        while (sz<=n) sz<<=1;
        a.assign(n+1,-inf-5);
        t.assign(2*sz-1,n);
        forn(i,n) t[sz-1+i]=i;
    }
    int merge(int i, int j) {
        if (a[i] >= a[j]) return i;
        return j;
    }
    void upd(int v, int l, int r, int i) {
        if (r-l==1) return;
        int m=(l+r)>>1;
        if (i<m) upd(2*v+1,l,m,i);
        else upd(2*v+2,m,r,i);
        t[v]=merge(t[2*v+1],t[2*v+2]);
    }
    void set(int i, int x) {
        a[i]=x;
        upd(0,0,sz,i);
    }
    int query(int v, int l, int r, int lx, int rx) {
        if (rx<=l || r<=lx) return a.size()-1;
        if (lx<=l && r<=rx) return t[v];
        int m=(l+r)>>1;
        int lq=query(2*v+1,l,m,lx,rx);
        int rq=query(2*v+2,m,r,lx,rx);
        return merge(lq,rq);
    }
    int query(int l, int r) {
        return query(0,0,sz,l,r);
    }
};

const int sz = 1<<21;
struct node {
    int L=-1,R=-1,s=0;
};

node t[(int)4e6];
int nxt=0;
int nw() {
    return nxt++;
}

int add(int v, int l, int r, int i) {
    if (r-l==1) {
        int z = nw();
        t[z].s = t[v].s+1;
        return z;
    }
    int m=(l+r)>>1;
    int z = nw();
    if (v==-1) {
        if (i<m) t[z].L = add(-1,l,m,i);
        else t[z].R = add(-1,m,r,i);
        t[z].s = 1;
        return z;
    }
    if (i < m) {
        t[z].L = add(t[v].L,l,m,i);
        t[z].s = t[v].s - t[t[v].L].s + t[t[z].L].s;
        t[z].R = t[v].R;
    } else {
        t[z].R = add(t[v].R,m,r,i);
        t[z].s = t[v].s - t[t[v].R].s + t[t[z].R].s;
        t[z].L = t[v].L;
    }
    return z;
}
int add(int v, int i) {
    return add(v,0,sz,i);
}
int sum(int v, int l, int r, int lx, int rx) {
    if (v==-1) return 0;
    if (rx<=l || r<=lx) return 0;
    if (lx<=l && r<=rx) return t[v].s;
    int m=(l+r)>>1;
    int lq = sum(t[v].L,l,m,lx,rx);
    int rq = sum(t[v].R,m,r,lx,rx);
    return lq+rq;
}
int sum(int v, int l, int r) {
    return sum(v,0,sz,l,r);
}

int rt[sz][2];

struct DSU {
    vector<int> p,sz;
    DSU(int n) {
        forn(i,n) p.pb(i),sz.pb(1);
    }
    int get(int u) {
        return (p[u]==u)?u:get(p[u]);
    }
    void uni(int u, int v) {
        u=get(u), v=get(v);
        if (u==v) return;
        if (sz[u]<sz[v]) swap(u,v);
        p[v]=u;
        sz[u]+=sz[v];
    }
};

void solve() {

    int n; cin>>n;
    vector<pi> a(n);
    forn(i,n) cin>>a[i].f>>a[i].s;
    sort(all(a));

    sgt st(n);
    forn(i,n) st.set(i,a[i].s);

    vector<int> vis(n),c(n);

    DSU dsu(n);
    forn(i,n) {
        vis[i]=1;
        int l=i, r=n-1;
        while (l<r) {
            int m=(l+r+1)>>1;
            if (a[m].f < a[i].s) l=m;
            else r=m-1;
        }
        st.set(i,-inf);
        while (1) {
            int j = st.query(i,r+1);
            if (vis[j]) break;
            if (a[j].s < a[i].s) break;
            vis[j]=1;
            st.set(j,-inf);
            c[j]=c[i]^1;
            dsu.uni(i,j);
        }
    }

    rt[0][0]=rt[0][1]=nw();

    forn(i,n) {
        rt[i+1][0]=rt[i][0];
        rt[i+1][1]=rt[i][1];
        rt[i+1][c[i]] = add(rt[i+1][c[i]],a[i].s);
    }

    int ok=1;
    forn(i,n) {
        int l=i, r=n-1;
        while (l<r) {
            int m=(l+r+1)>>1;
            if (a[m].f < a[i].s) l=m;
            else r=m-1;
        }
        int z = sum(rt[r+1][c[i]],a[i].s+1,sz) - sum(rt[i][c[i]],a[i].s+1,sz);
        if (z) ok=0;
    }
    int ans=1;
    set<int> s; forn(i,n) s.insert(dsu.get(i));
    forn(i,s.size()) ans=(2*ans)%mod;
    cout<<ans*ok<<'\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;
}

컴파일 시 표준 에러 (stderr) 메시지

port_facility.cpp:4:1: warning: multi-line comment [-Wcomment]
    4 | //   \ __ __  \
      | ^
port_facility.cpp: In function 'void solve()':
port_facility.cpp:100:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 | #define forn(i,n) for(int i=0; i<(n); ++i)
      |                                 ^
port_facility.cpp:292:5: note: in expansion of macro 'forn'
  292 |     forn(i,s.size()) ans=(2*ans)%mod;
      |     ^~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 56
• Subtask 4: 0 / 22