/*
⣷⠄⠄⠘⡄⠘⡀⠹⣿⠛⢿⣏⠈⢿⠈⠻⣧⠈⢿⠋⠉⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡀⠄⠘⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠟⠁⠁⠄⢀⣾⣿⣿⣿⣿⣿⣿⡟⠁⣼⡇⠄⣿⣿⠄⢸⠇⢠⠇⢰⠁⠄⠄⣿⡿⠄⣿⣿⡿⠄⠄⢀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⡀⠄⠄⢳⡀⠐⡀⠹⣧⠈⢿⣇⠈⢧⠄⠹⣧⠄⠄⠄⠄⠈⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⠄⠄⠹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠛⠁⠄⠄⣠⣶⣿⣿⣿⣿⣿⣿⣿⡟⠄⠐⣿⡇⠄⣿⡏⠄⣼⠄⢸⠄⢸⠄⠄⢰⣿⡇⠄⠃⢸⡇⠄⠄⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣇⠄⠄⠈⣧⠄⢱⠄⢻⡆⠈⣿⣆⠈⢧⠄⢹⣧⠄⠄⠄⠄⠄⠙⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⡄⠄⠈⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠟⠋⠄⠄⢀⣴⣾⣿⣿⣿⣿⣿⣿⣿⣿⠟⠄⣰⠄⢸⡇⢸⣿⡇⠄⣿⠄⡀⠄⡄⠄⠄⢸⣿⠁⠄⠄⣿⡇⠄⠄⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⠄⠄⠄⢻⣇⠄⢧⠄⢻⡀⠸⣿⡆⠈⣧⠄⢻⣧⠄⠄⠘⣦⠄⠈⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⠄⠄⠙⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠟⠁⠄⠄⣠⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠏⠄⣰⣿⡇⢸⡇⢸⣿⠄⠄⡇⠄⡇⠄⡇⠄⠄⢸⡿⠄⠄⢠⣿⠄⠄⠄⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣇⠄⠄⠈⢿⡄⠘⣇⠄⢧⠄⢿⣿⡄⠘⣧⠄⢿⣷⣶⡀⠸⣧⡀⠈⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⠄⠈⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⠁⠄⠄⣠⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠏⠄⠄⢻⣿⠄⢸⡇⢸⣿⡆⢸⡇⢀⡇⠄⠁⠄⠄⢸⡇⠄⠄⢸⣿⠄⠄⠄⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⡀⠄⠄⠄⢳⠄⢹⣆⠈⣧⣸⡿⠟⠄⠉⠁⠄⣉⣿⣿⣤⣿⣷⡀⠄⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⡀⠄⠈⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠋⠄⠄⣠⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠏⠄⣰⡀⠈⠟⠁⢀⣀⣀⣀⣀⣀⠄⠈⠃⠄⠄⠄⠄⢸⠃⠄⠄⣿⡟⠄⠄⢀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⡇⠄⠄⠄⠄⢣⠄⢻⡄⠈⠁⠄⠠⠶⢶⣾⣿⣿⣿⣿⣿⣿⣿⣿⡄⠄⠹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣀⠄⠹⠿⠿⠿⠛⠛⠛⠛⠛⠛⠿⢿⣿⣿⡿⠁⠄⣠⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃⠄⣰⣿⣿⣶⣶⣾⣿⣿⣿⣿⣿⣿⣿⡇⠄⣿⠄⢰⠄⢸⠄⠄⠄⣿⡇⠄⠄⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⠄⠄⠄⢳⠄⢂⠈⣷⣄⣤⣤⠄⠄⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣄⠄⢹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣀⠄⠄⠄⠄⢀⣀⣀⡀⠄⠄⠄⠈⠉⠄⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃⠄⣰⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣤⣄⡀⠘⠄⢸⠄⡇⠄⣿⠇⠄⠄⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⡆⠄⠄⠘⣧⠈⢦⡘⣿⡿⠃⢀⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣶⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣾⣿⣿⣿⣿⣿⣿⣿⣷⣶⣤⣤⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠇⠄⣰⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠟⠛⠒⠄⣿⣿⡇⠄⣿⠄⠄⠄⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⠄⠄⠄⠻⣧⠈⣿⡿⠁⢠⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠏⠄⣰⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⡀⠹⣿⡇⢹⡇⢸⡟⠄⠄⠄⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⡇⠄⠄⠄⠹⣆⠘⠃⢀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡏⠄⣰⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⡀⠘⡇⢸⡇⢸⡇⠄⠄⢠⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⠄⠄⠄⠄⢻⣆⠄⠘⠋⠉⣿⣿⣿⣿⣿⣿⣿⣿⣷⣶⣄⠈⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠛⠛⠛⠛⣻⣿⣿⣿⣿⣿⣿⡿⠿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⠄⣰⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⠄⠄⢸⡇⠈⠁⠄⠄⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣇⠄⠄⠰⡀⢻⣦⠄⠄⣸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠄⠈⣿⣿⣿⣿⣿⣿⡿⠟⠛⠉⢀⣴⣶⣿⣿⣿⣿⣿⣿⣿⣿⠟⠁⢀⣤⣾⣿⣿⣿⣿⡿⠿⢿⠿⠻⠿⠿⠿⠿⣿⣿⣿⣿⡿⠄⢠⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⠄⢸⡇⠄⠄⠄⠄⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⡀⠄⠄⣷⣤⣿⠄⢀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠄⣿⣿⠿⠛⠋⠁⠄⢀⣠⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃⠄⠄⣿⣿⣿⣿⣿⣿⣿⣷⣦⣄⠄⠄⢄⡀⠄⢤⣀⣉⡙⠛⠁⢠⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠛⠋⠉⠙⡇⠄⡇⠄⠄⠄⠄⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣧⠄⠄⢸⣿⡇⠄⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠇⠄⠋⠁⠄⠄⢀⣤⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃⢀⠄⢀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⡀⠙⠄⠄⠻⣿⣿⣷⣶⣿⣏⠛⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃⢀⠄⢸⡇⠄⡇⠄⣇⠄⠄⠄⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⡄⠄⠄⣿⠁⠄⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⠁⠄⠄⣠⠔⠁⣠⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠄⣾⠄⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⡀⠄⠄⠘⢿⣿⣿⣿⣿⣿⣶⣌⠙⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠇⠄⣾⠄⢸⣷⠄⣿⠄⢿⠄⠄⠄⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣧⠄⠄⢹⠄⠘⣿⣿⣿⣿⣿⣿⣿⡿⠁⡀⠄⠄⣠⡾⠃⢠⣾⣿⣿⣿⣿⣿⣿⣿⡿⠛⣿⣿⣿⣿⣿⣿⣿⡇⠄⣿⠄⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⡀⠄⠈⢿⣿⣿⣿⣿⣿⣿⣷⣄⠘⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠄⠄⢹⠄⣸⣿⠄⣿⠄⢸⠄⠄⠄⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⡄⠄⠘⣷⠖⢿⣿⣿⣿⣿⣿⣿⠁⣼⠃⢀⣾⡟⠁⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⠁⢰⣿⣿⣿⣿⣿⣿⣿⡇⠄⣿⠄⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⡀⠄⠻⣿⣿⣿⣿⣿⣿⣿⣦⠈⠉⠙⠿⣿⣿⣿⡿⠁⠈⠉⠄⠄⣻⣿⣿⣿⣤⣿⠄⢸⠄⠄⠄⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⠄⠄⢿⣆⠈⢻⣿⣿⠏⡉⠁⠄⠃⢀⣾⠋⢠⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃⢀⣿⣿⣿⣿⣿⣿⣿⣿⡇⠄⣿⠄⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣆⠄⠙⢿⣿⣿⣿⣿⣿⣿⣧⢀⡀⠄⡈⠙⠋⠄⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣾⠄⠄⢰⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡀⠄⢸⣿⣆⠄⠛⠃⢀⣿⣿⠆⠄⡼⠁⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡏⠄⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⠄⢸⠄⠸⣿⣿⣿⣿⣿⣿⣿⠄⢸⣿⡟⢻⣿⣿⣿⣿⣿⣿⣿⣿⣦⣠⣬⣿⣿⣿⣿⣿⣿⣿⣿⣷⡄⠹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠄⠄⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⠄⠘⣿⣿⣷⣶⣾⣿⣿⡟⠄⠄⠄⣸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠄⢸⣿⣿⣿⣿⣿⡏⠄⣿⣿⣿⣇⠄⠁⠄⣿⣿⣿⣿⣿⣿⣿⠄⢸⣿⡇⠄⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡄⠈⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠄⠈⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⡏⠄⠄⠄⣿⣿⣿⣿⣿⣿⣿⠁⠄⠄⣰⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠄⣼⣿⣿⣿⣿⣿⡇⠄⣿⣿⣿⣿⣦⡀⠄⣿⣿⣿⣿⣿⣿⣿⠄⢸⣿⣧⠄⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡄⠈⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠄⠄⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⠁⠄⠄⢠⣿⣿⣿⣿⣿⣿⡇⠄⠄⣰⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃⢠⣿⣿⣿⣿⣿⣿⡇⠄⣿⣿⣿⣿⣿⣿⣶⣿⣿⣿⣿⣿⣿⣿⠄⢿⣿⣿⠄⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⠈⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠁⠄⠄⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⡆⠄⠄⣿⣿⣿⣿⣿⣿⣿⠄⠄⣰⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠄⢸⣿⣿⣿⣿⣿⣿⣿⠄⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠄⢸⣿⣿⡆⠸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣆⠄⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠄⠄⠄⠘⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⠁⠄⢀⣿⣿⣿⣿⣿⣿⣿⣀⣠⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⠄⢸⣿⣿⠟⢿⣿⣿⣿⠄⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠛⣿⣿⣿⠄⢸⣿⣿⡇⠄⢿⣿⣿⣿⣿⣿⠙⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⠄⠄⠄⠄⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⠄⠄⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠁⠄⠄⣿⣿⠃⠄⠄⢻⣿⣿⠄⢹⣿⣿⣿⣿⣿⣿⣿⣿⣿⠄⣿⣿⣿⠄⠄⢻⣿⡇⠄⠘⣿⣿⣿⣿⣿⡀⠈⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠄⠄⠄⠄⠘⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⠄⠄⣸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃⠄⠄⠄⣿⡟⠄⠄⡀⠈⣿⣿⠄⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⠄⢹⣿⣿⠄⠄⠈⣿⡇⠄⡄⠘⣿⣿⣿⣿⡇⠄⠘⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣇⡀⠄⡄⠄⠄⢹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⠄⠄⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠇⠄⠄⡄⠄⣿⠃⠄⢸⣧⠄⠸⣿⠄⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⠄⢸⣿⣿⠄⠄⠄⢹⡇⠄⣿⡄⠘⣿⣿⣿⡇⠄⠄⢹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠄⣿⠄⠄⠘⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⠄⠄⢹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⠄⠄⣼⡇⢰⡏⠄⠄⣿⣿⡆⠄⢿⡇⠈⣿⣿⣿⣿⣿⣿⣿⣿⣿⠄⢸⣿⣿⠄⢸⡄⠈⠇⢀⣿⣷⠄⠸⣿⣿⣿⠄⣄⠄⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣿⣿⣿⣿⣿⣿⣿⡇⠄⣿⡇⠄⠄⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⡏⠄⠄⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⠄⠄⢰⣿⡇⠈⠁⠄⣸⣿⣿⣷⠄⠘⠁⠄⢻⣿⣿⣿⣿⣿⣿⣿⣿⠄⢸⣿⣿⠄⢸⣷⠄⠄⢸⣿⣿⣧⠄⠹⣿⣿⠄⢹⡀⠘⢿⣿⣿⣿⣿⣿⡟⠙⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠄⢸⣿⣿⣿⣿⣿⣿⡇⠄⣿⣿⠄⠄⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⡇⠄⠄⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠄⠄⠄⣿⣿⡇⠄⠄⠄⣿⣿⣿⣿⡆⠄⠄⡄⠈⣿⣿⣿⣿⣿⣿⣿⣿⠄⢸⣿⣿⠄⢸⣿⣧⡀⢸⣿⣿⣿⣇⠄⢻⣿⡇⢸⣇⠄⠘⣿⣿⡿⠛⠁⡀⠄⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠄⢸⣿⣿⣿⣿⣿⣿⡇⠄⠉⠻⠄⠄⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⡇⠄⠄⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⠄⠄⠄⢸⣿⣿⡇⠄⠄⢸⣿⣿⣿⣿⣿⠄⠄⣿⠄⢹⣿⣿⣿⣿⣿⣿⣿⡄⢸⣿⣿⠄⢸⣿⣿⣧⣸⣿⣿⣿⣿⣆⠄⢿⠇⠈⢻⡀⠄⠙⠁⣀⣴⣾⣧⠄⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠄⣾⣿⣿⣿⣿⣿⣿⠁⢠⣦⣄⠄⠄⠄⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣯⠄⠄⣸⣿⣿⣿⣿⣿⣿⣿⠋⢻⣿⣿⣿⣿⣿⣿⡿⠄⠄⠄⠘⢿⣿⡇⠄⠄⢸⣿⣿⣿⣿⣿⡇⣰⣿⡇⠸⣿⣿⣿⣿⣿⣿⣿⡇⢸⣿⣿⠄⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣆⠄⠄⠠⠄⠁⠄⠄⢸⣿⣿⣿⣿⠄⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⠄⣿⣿⣿⣿⣿⣿⣿⠄⠄⠈⠙⠃⠄⠄⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣗⠄⠄⣿⣿⣿⣿⣿⣿⣿⡏⠄⣸⣿⣿⣿⣿⣿⣿⠇⢠⣶⣶⣤⡀⠈⠃⠄⠄⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠄⠘⣿⣿⣿⣿⣿⣿⡗⠈⣿⣿⠄⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠓⠄⣀⣤⠄⠄⠄⠄⢿⣿⣿⣿⡄⢸⣿⣿⣿⣿⣿⣿⣿⣿⡏⠄⣿⣿⣿⣿⣿⣿⡟⠄⠸⣷⠦⠄⠄⠄⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⠄⠄⣿⣿⣿⣿⣿⣿⣿⡇⠄⣿⣿⣿⣿⣿⣿⡏⠄⣾⣿⣿⣿⣿⣷⣤⡀⠄⠙⠻⣿⣿⣿⣿⣿⣿⣿⣿⣇⠄⠈⢿⣿⣿⣿⣿⣧⠄⣿⡟⠄⢸⣿⣿⣿⣿⣿⣿⠿⠋⠁⣠⣴⣾⣿⣿⣇⢰⣄⠄⠸⣿⣿⣿⣇⠄⢻⣿⣿⣿⣿⣿⣿⣿⡇⠄⣿⣿⣿⣿⣿⣿⡇⠄⢠⣀⣠⡀⠄⠄⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⠄⠄⣿⣿⣿⣿⣿⣿⣿⠁⢠⣿⣿⣿⣿⣿⡿⠄⢸⣿⣿⣿⣿⣿⣿⣿⣿⡀⣤⣀⠄⠙⢿⣿⣿⣿⣿⣿⣿⣦⠄⠘⣿⣿⣿⣿⣿⠄⢹⠃⠄⣼⣿⣿⣿⠛⠉⣀⣤⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⡆⠄⢿⣿⣿⣿⡄⠈⣿⣿⣿⣿⣿⣿⣿⡇⠄⣿⣿⣿⣿⣿⣿⣷⠄⠾⠟⠋⠁⠄⢠⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⡆⠄⣿⣿⣿⣿⣿⣿⡟⠄⣸⣿⣿⣿⣿⣿⠇⠄⠛⠛⠻⠿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣦⣀⣽⣿⣿⣿⣿⣿⣿⣇⠄⠸⣿⣿⣿⣿⠄⠄⠄⠄⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⠄⠘⠿⠿⣿⣷⠄⢹⣿⣿⣿⣿⣿⡿⠃⢸⣿⣿⣿⣿⣿⣿⡿⠄⣤⣤⣶⠄⠄⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠄⢹⣿⣿⡿⢿⣿⠃⢀⣿⣿⣿⣿⣿⡿⠄⣀⠄⠄⠄⠄⠄⠉⠛⠿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣆⠄⠙⣿⣿⣿⠄⢠⣤⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠿⠛⠛⠉⠄⠄⠄⠄⠄⢀⡀⠈⣿⣿⣿⣿⣿⡇⠄⢸⣿⣿⣿⣿⣿⣿⡇⠄⣿⣿⣿⠄⠄⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⠄⠄⢸⣿⣿⡇⠈⣿⠄⢸⣿⣿⣿⣿⣿⡇⠄⣿⣿⣶⣤⣀⠄⠄⠄⠄⠄⠈⠙⠛⠿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⡀⠘⢿⣿⠄⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠟⠛⠉⠄⠄⠄⠄⠄⠄⢀⡀⠄⠄⣶⣿⣷⠄⢻⣿⣿⣿⣿⡇⠄⣿⣿⣿⣿⣿⣿⣿⡇⠄⣿⣿⣿⠄⠄⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠄⠄⣿⣿⡇⠄⡏⠄⢸⣿⣿⣿⣿⣿⠁⢸⣿⣿⣿⣿⣿⣿⣷⣦⣤⣀⡀⠄⠄⠄⠄⠉⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣄⠄⠙⠂⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⠋⠄⠄⠄⠄⠄⠄⣀⣤⣶⣾⣿⣿⣷⡀⠄⢻⣿⣿⡄⠘⣿⣿⣿⣿⡇⠄⣿⣿⣿⣿⣿⣿⣿⠃⠄⣿⣿⣿⡇⠄⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⠄⠄⢻⣿⡇⠄⣿⠄⢸⣿⣿⣿⣿⡿⠄⣸⣿⣿⣿⣿⣿⣿⠿⠛⠉⠁⠄⠄⠄⠄⠄⢀⣀⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣄⣈⣿⣿⣿⣿⣿⣿⣿⣿⣏⠄⠄⠄⠄⠄⠘⠻⣿⣿⣿⣿⣿⣿⣿⣷⠄⠘⣿⣿⣧⠄⢿⣿⣿⣿⡇⠄⣿⣿⣿⣿⣿⣿⣿⠄⢰⣿⣿⣿⡇⠄⠸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡄⠄⢸⣿⡇⠄⢸⠄⢸⣿⣿⣿⣿⡇⠄⣿⣿⡿⠟⠋⠁⠄⠄⠄⠄⠄⣀⣠⣴⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣤⣀⠄⠄⠄⠄⠄⠉⠉⠛⠛⠿⢿⣿⡇⠄⢿⣿⣿⡀⢸⣿⣿⣿⡇⠄⢻⣿⣿⣿⣿⣿⣿⠄⢸⣿⣿⣿⣇⠄⠄⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣇⠄⠸⣿⣿⠄⢸⠄⢸⣿⣿⣿⣿⠃⢰⣿⠁⠄⠄⠄⠄⣀⣤⣴⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣶⣦⣤⣀⡀⠄⠄⠄⠄⠄⠈⠁⠄⠸⣿⣿⣇⠄⠻⣿⣿⡇⠄⢸⣿⣿⣿⣿⣿⣿⠄⣼⣿⣿⣿⣿⠄⠄⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡀⠄⢻⣿⠄⠈⠄⢸⣿⣿⣿⡿⠄⣼⣿⡷⠄⠒⢸⠏⠉⣿⠟⢹⠏⠉⠟⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠿⠛⠋⠉⠛⠛⠛⠿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠛⠙⡿⠛⠋⠹⠓⡢⠄⠄⡀⠄⡀⠄⢸⣿⣿⡀⠄⣿⣿⡇⠄⢸⣿⣿⣿⣿⣿⡿⠄⣿⣿⣿⣿⣿⡄⠄⢹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⠄⠈⢿⡆⠄⠄⠸⣿⣿⣿⡇⠄⠄⡟⠁⠄⢀⡞⠄⣰⠃⠄⠄⠄⠄⢀⣾⣿⣿⣿⣿⣿⣿⠟⢁⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠈⠻⣿⣿⣿⠟⠁⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠈⢀⣼⠇⠄⠄⢻⣿⡇⠄⣿⣿⡇⠄⢸⣿⣿⣿⣿⡿⠁⢰⣿⣿⣿⣿⣿⡇⠄⠄⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣆⠄⠘⢿⡀⠄⠄⣿⣿⣿⠁⠄⡜⠄⠄⢀⡞⠄⡰⠁⠄⠄⠄⠄⢠⣾⣿⣿⣿⣿⣿⣿⠇⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠘⣿⣿⠄⠄⡀⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⡰⠊⠄⠄⠄⠄⠄⢿⡇⠄⣿⣿⡇⠄⢸⣿⣿⣿⠟⠄⠄⢸⡿⠛⣿⣿⣿⣧⠄⠄⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠋⠄⠄⠄⠁⠄⠄⢸⣿⣿⠄⠘⠄⠄⢀⡞⢀⣴⠃⢀⣤⣴⣿⣾⣿⣿⣿⣿⣿⣿⣿⣿⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⢻⣿⣤⣾⣥⡀⣀⠄⣠⠂⠄⠄⠄⡠⠊⠄⠄⠄⢀⣴⠄⠄⢸⡇⠄⣿⣿⡇⠄⢸⡿⠃⠄⣴⡇⠄⠈⢀⣼⣿⣿⣿⣿⠄⠄⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡏⠄⠄⠄⠄⠄⠄⠄⠄⢿⣿⠄⢰⣾⣶⣿⣷⣾⣿⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠈⣿⣿⣿⣿⣿⣿⣿⣿⣶⣦⣤⣎⣀⡄⠄⣠⣶⣿⣿⡆⠄⠄⠇⢠⣿⣿⣧⠄⠈⢀⡄⠄⢻⡇⠄⠄⣾⣿⣿⣿⣿⣿⡆⠄⠄⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠄⠄⠄⣸⡇⠄⠄⠄⠄⠉⠄⠘⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⢹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣇⠄⠄⢀⡀⠈⠄⣀⠄⣾⣿⣷⠄⢸⡇⠄⠄⡿⢿⣿⣿⣿⣿⡇⠄⠄⢹⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠇⠄⠄⢠⣿⠄⠄⣿⣿⣶⣿⣇⠄⠈⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⣀⣀⣀⣤⣤⣀⡀⠄⠄⠘⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡄⠄⢸⣿⣿⣿⣿⠄⠹⠋⣩⠄⢸⣧⠄⠄⢀⣾⣿⣿⣿⣿⣿⠄⠄⠘⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠄⠄⠄⣸⣿⠄⠄⣿⣌⠛⢿⣿⠄⠄⠄⠙⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠄⠄⠄⠄⠄⠄⠄⠄⠄⢀⣠⣶⣾⣿⣿⣿⣿⣿⣿⣿⣷⣆⠄⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠟⠉⠁⠄⣼⣿⣿⣿⣿⠄⢰⣿⣿⡄⠈⡏⠄⠄⢾⣿⣿⣿⣿⣿⣿⡆⠄⠄⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠄⠄⠄⣿⡟⠄⠄⣿⣿⣷⣦⣽⡄⠄⣿⠄⡀⠉⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠄⠄⠄⠄⠄⠄⢀⣴⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠄⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠛⠉⢀⡤⠄⠄⠄⠄⣿⣿⣿⣿⣿⡇⠸⣿⡟⣁⠄⠛⠄⠄⠸⠋⢸⣿⣿⣿⣿⣷⠄⠄⢸⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣟⠄⠄⠄⢰⣿⡇⠄⠄⣉⣉⣉⠙⣻⡇⠄⠹⠄⢻⠄⢀⠈⠙⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠄⠄⠄⠄⢀⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡆⠸⣿⣿⣿⣿⣿⣿⣿⣿⡿⠋⠁⠄⠄⠄⠄⢀⡴⠇⠄⠄⣿⣿⣿⣿⣿⡇⠄⣿⣾⡿⠃⠄⠄⠄⠄⣠⣿⣿⣿⣿⣿⣿⡆⠄⠄⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⠇⠄⠄⠄⣼⣿⡇⠄⠄⣿⣿⣿⣿⣿⡇⠄⠄⠄⢸⠄⢸⣷⣦⣄⡈⠉⠛⠿⣿⣿⣿⣿⣿⣿⣿⣿⡆⠄⢀⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠄⣿⣿⣿⣿⣿⡿⠟⠋⠁⠄⠄⠄⠄⠄⠄⠋⠄⡀⠄⠄⣿⣿⣿⣿⣿⡇⠄⣿⠏⢀⣴⣆⠄⠄⠄⢿⠟⢉⣿⣿⣿⣿⣿⡀⠄⠹⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⡿⠄⠄⠄⢀⣿⣿⡇⠄⠄⣿⣿⣿⣿⣿⡇⠄⠄⠄⢸⠄⢸⣿⣿⣿⣿⣿⣶⠄⠄⠈⠛⠿⢿⣿⣿⣿⣧⠄⢹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠄⣿⡿⠿⠋⠁⠄⠄⣠⣿⠁⠄⠄⠄⠄⠄⠰⠋⠄⠄⠄⣿⣿⣿⣿⣿⡇⠄⢁⣴⣿⣿⡿⠄⠄⠄⠄⣠⣾⣿⣿⣿⣿⣿⣧⠄⠄⠙⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⡟⠄⠄⠄⣸⣿⠟⠋⠄⠄⢸⣿⣿⣿⣿⡇⠄⠄⠄⢸⠄⣾⣿⠟⢉⣴⠟⢉⠄⠄⠄⠄⣤⣄⣀⠉⠉⠛⠄⠄⠿⠿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠿⠛⠛⠋⠁⠄⠄⠄⣀⣤⣴⣾⡿⠋⠁⠄⠄⠄⠄⠄⠄⢠⣶⡇⠄⠄⣿⣿⣿⣿⣿⡇⠄⣿⣿⠟⠉⣀⡆⠄⠄⠄⣿⠟⣻⣿⣿⣿⣿⣿⣆⠄⠄⢹⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⡇⠄⠄⢠⣿⠏⠄⡰⠄⠄⢸⣿⣿⣿⣿⡇⠄⠄⠄⣾⡴⠛⢁⣴⠟⠁⣠⣿⠄⠄⠄⠄⢸⡿⠋⢀⣴⡿⠖⣤⣤⡄⣀⣀⡀⠄⠄⠉⠉⠉⠁⠄⠄⠄⠄⣤⣶⣶⣿⣿⡇⠄⢹⣿⣿⠟⠁⠄⢀⣤⠄⠄⠄⠄⠄⠘⠋⠄⠄⢸⣿⣿⣿⣿⣿⡇⠄⡟⠁⣠⣾⠿⣣⡀⠄⠄⠄⣴⡿⠻⣿⣿⣿⣿⣿⡄⠄⠈⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⡿⠄⠄⠄⣼⣿⠄⠄⢁⠄⠄⢸⣿⣿⣿⣿⡇⠄⢠⡠⠋⣀⣴⠟⠁⣠⣾⡿⠟⠄⠄⠄⠄⠄⢀⣴⡿⠋⢀⣴⠟⠁⣠⣿⣿⡇⠄⠄⠄⠄⠄⣀⣀⣤⣶⣿⣿⣿⣿⣿⣿⡇⠄⢸⠟⠁⠄⢀⣴⠟⠁⡀⠄⠄⠄⠄⢠⡴⠃⠄⢸⣿⣿⣿⣿⣿⡇⠄⣷⡿⠋⣡⣾⣿⡇⠄⠄⢸⠟⢀⣼⣿⣿⣿⣿⣿⣧⠄⠄⢸⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⠇⠄⠄⢰⣿⠏⢀⡴⠛⠄⠄⢻⣿⣿⣿⣿⡿⠄⢈⣠⣾⡟⠁⣠⣾⡿⠋⢀⣴⠄⠄⠄⠄⣾⡿⠋⢀⣴⠟⠁⣠⣾⣿⣿⣿⣷⠄⠄⠄⢰⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠃⠄⠰⡞⢀⣴⠟⠁⡠⠊⠄⠄⠄⠄⠄⢸⣤⣤⠄⣿⣿⣿⣿⣿⣿⡇⠄⢋⣠⣾⣿⡿⠋⣀⠄⠄⠄⣠⣾⣿⣿⣿⣿⣿⣿⣿⡄⠄⠄⣿⣿⣿
⣿⣿⣿⣿⣿⣿⡿⠄⠄⢠⣿⣿⣾⠟⢀⣴⡇⠄⠸⣿⣿⣿⣿⡇⠄⣸⣿⠋⣠⣾⡿⠋⢀⣤⡿⠿⡇⠄⠄⠄⠋⠄⣰⠟⠁⣠⣾⣿⣿⡿⠟⠛⠁⠄⠄⠄⢸⣿⣿⣿⣿⣿⣿⣿⡿⠛⠁⣠⣶⡄⠄⡀⠙⠳⢤⡞⠄⣠⠞⠁⠄⠄⠄⠄⢸⣿⠄⢸⣿⣿⣿⣿⣿⡇⢰⣿⣿⡿⠋⣠⣾⣿⠄⠄⠄⠹⠋⣻⣿⣿⣿⣿⣿⣿⣧⠄⠄⢸⣿⣿
⣿⣿⣿⣿⣿⣿⡇⠄⢀⣾⣿⣿⠋⣠⡾⠋⣡⠄⢀⣀⣀⠄⠈⠄⠄⢻⣿⣾⡿⠋⢀⣴⡿⠋⣠⣾⡇⠄⠄⢠⣴⠞⠁⣠⣾⣿⠿⠛⠉⠄⣠⣴⣿⣿⡆⠄⣾⣿⣿⣿⣿⣿⡿⠉⢀⣠⣾⣿⣿⣇⣼⣿⠆⣤⣀⠈⠙⠁⢠⡶⠄⠄⠄⢀⣾⣿⠄⠘⣿⣿⣿⣿⣿⠇⢸⡿⠋⣠⣾⣿⠟⣿⡆⠄⠄⠄⣾⣿⣿⣿⣿⣿⣿⣿⣿⡄⠄⠄⣿⣿
⣿⣿⣿⣿⣿⣿⠄⢠⣿⣿⣿⣧⡾⠋⣠⣾⣿⠄⣼⣿⣿⣿⣿⡇⠄⣿⣿⠋⢀⣴⡿⠋⢀⣾⣿⠟⢻⡀⠄⠸⠃⣠⣾⡿⠋⢀⣠⣴⣾⣿⣿⣿⣿⣿⣿⣶⣿⣿⣿⣿⣿⣟⣁⣴⣿⣿⣿⣿⣿⣿⣿⣿⣾⣿⣿⣿⣷⣦⣄⣀⠘⠋⠄⣈⠉⠙⠄⢀⡈⠙⠛⠉⣹⠄⣋⣤⣾⣿⢟⣡⣾⣿⣷⣄⢠⣤⣿⣉⣸⣿⣿⣿⣿⣿⣿⣷⠄⠄⢸⣿
*/

const start = new Date()
console.log(start);
require("./requires")

// loading functions
commands = new Map()

var path = `${__dirname}/functions`
var folders = fs.readdirSync(path).filter(function (file) {
    return fs.statSync(path+'/'+file).isDirectory();
});
folders.forEach(element => {
    var commandFiles = fs.readdirSync(`${__dirname}/functions/${element}`).filter(file => file.endsWith('.js') && !file.startsWith("index"));

    for (const file of commandFiles) {
        const command = require(`./functions/${element}/${file}`);
        commands.set(command.name, command);
    }
});

// General stuff
var platform    = process.platform;

// Express
const express = require("express");
const app = express()
const port = 3777

app.use(bodyParser.urlencoded({
    extended:true
}));

// For monitoring
app.get('/api/v1/health', async (req, res) => {
    if(await ratelimiter(req, res))return
    res.json({
        response:"okay",
        startup:await commands.get("readableTime").timestamp(start),
        uptime:await commands.get("readableTime").timeframe(new Date().getTime() - start.getTime())
    })
})

// Functionality

/*
// This is the code used for the rate limiter and ban system
// If you need to do changes, do them here
*/


async function ratelimiter(req, res){
    return new Promise(async (resolve) => {

        let rl = false;
        await commands.get("ratelimit").function(req).catch(err => {
            rl = true;
            switch(err){
                case 1: res.json({code:1});return
                case 2: res.json({code:2});return
                case 3: return
            };
        })
        resolve(rl);
    })
}





// As for the banhandler and ratelimiter, i wasnt able to come up with a better way to implement it here so that i wont need all these repeating lines
// If you have a better way to do it, feel free to tell me
// GET
app.get('/api/v1/info/:shortcode', async (req, res) => {
    // Endpoint to get information about a shortcode
    if(await ratelimiter(req, res))return
    commands.get("info").function(req, res)
})

app.get('/api/v1/codeList', async (req, res) => {
    // Endpoint to get information about a shortcode
    if(await ratelimiter(req, res))return
    commands.get("codeList").function(req, res)
})

app.get('/api/v1/test', async (req, res) => {
    // Testing endpoint uwu
    if(await ratelimiter(req, res))return
    res.status(418)
    res.send("I am a teapot, leave me alone")
})

// POST
app.post('/api/v1/createUser', async (req, res) => {
    // Endpoint to create user account
    if(await ratelimiter(req, res))return
    commands.get("createUser").function(req, res)
})

app.post('/api/v1/authenticate', async (req, res) => {
    // Endpoint to create API key
    if(await ratelimiter(req, res))return
    commands.get("authenticate").function(req, res)
})

app.post('/api/v1/createCode', async (req, res) => {
    // Endpoint to create API key
    if(await ratelimiter(req, res))return
    commands.get("createCode").function(req, res)
})

// DELETE
app.delete('/api/v1/deleteCode', async (req, res) => {
    // Endpoint to delete shortcodes
    if(await ratelimiter(req, res))return
    commands.get("deleteCode").function(req, res)
})



// Main Page Handler
app.use(express.static(__dirname+"/webui"))
app.use(express.static(__dirname+"/webui/favicon.ico"))
app.use(express.static(__dirname+"/webui/stuff"))
app.use(express.static(__dirname+"/webui/pages"))






// REDIRECTION HANDLER
app.get('/:shortcode', async (req, res) => {
    // Endpoint to get information about a shortcode
    if(await ratelimiter(req, res))return
    if(!(req.params.shortcode.match(/^\w{3,18}$/))){
        console.log(req.params.shortcode + " Did not match");
        return
    }
    commands.get("redirect").function(req, res)
})






app.listen(port, () => {
    commands.get("Startup_function").function()
    console.log(`------------------------------------ Status ------------------------------------ \n` +
    `${__dirname} \n` +
    `${platform} \n` +
    `Listening on port ${port} \n` +
    `The Startup took ${new Date() - start}ms \n` +
    `${commands.size} modules loaded`);
})


const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});


rl.on("line", data =>{
    const args = data.trim().split(" ");
    const command = args.shift().toLowerCase();
    switch(command){
        case "exit":
            process.exit(1);
        break;
        case "reload":
            commands.get("reloadCommands").function()
        break;
        default:
            console.log("This is not a recognised command");
        break;
    };
})



// catch uncaught exceptions to prevent process crashes on random bugs
process.on("uncaughtException", (err) => {
    // console.log(process.stderr);
    console.error(err.stack);
    // console.error(err.stack.length);
    // try{
    //     commands.get("queryCommand").function("INSERT INTO tbl_errorlog (dtError) VALUES (?)",[err.stack])
    // }catch(error){
    //     console.log(error);
    // }
})