// Author: Ivan Teo
// Created: Mon Dec 9 17:34:46 2024
#define TASKNAME "678513B"
/*
⣿⣧⢿⣏⢻⣿⣦⣿⣿⣿⣿⣏⣿⣿⣾⣿⣿⣿⣾⣿⣿⣻⣿⣿⢿⡿⣿⢹⠁⢹⣾⣷⣧⣿⢽⣿⣿⣿⣿⣾⣿⣿⣿⣿⣿⣿⣿⣿⣏⣶⣿⣿⣿⣿⣿⣯⣿⣿⣿⣿⣿⣧⣿⣿⣏
⣿⣿⡜⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣽⣿⣿⣿⣯⣿⣿⣿⣿⢾⣿⣿⣾⡇⢸⣿⣿⣿⣿⢽⣿⣿⣿⣟⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣽⣿⣿⣿
⣿⣿⣷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⣿⣿⣿⣿⣿⣿⢸⣿⣿⣿⣿⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣏⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣿⣿⣿⣿⣿⣿⣿⣻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠓⠈⣫⠝⠛⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠋⠁⠁⠃⠸⡿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⠃⠋⠁⣠⠞⠁⠀⠀⠀⠈⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠋⠀⠀⠀⠀⠀⠀⠀⠹⠻⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⡝⢇⠔⢃⠜⠁⠀⠀⠀⠀⠀⠀⠀⠘⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠲⣴⠏⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⡿⢹⢔⣵⡿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠟⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⡻⣷⣾⢻⣿⣿⣿⣿⣿⣿⣿⡿⣿
⣿⣿⣿⣿⣿⣿⡟⢧⣷⣿⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⣿⣿⣿⣿⣿⣿⣿⣿⣿⠟⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠱⡻⡿⣾⢿⣿⣿⣿⣿⣿⣿⢣⣯
⢸⣿⣿⣿⣿⣿⣣⣫⣿⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⣿⣿⣿⣿⣿⣿⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢱⣿⣿⣦⣻⣿⣿⣿⣿⣿⣴⣿
⣿⣿⣿⣿⣿⢙⠝⣿⡏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢿⣿⣿⣿⡟⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠃⢷⡿⣟⣽⣿⣿⣿⣷⣿⣿
⣾⣿⣿⡿⠉⢊⣾⣿⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣿⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢿⣜⠉⢻⣿⣿⣿⣿⡾
⣿⣿⣿⡇⠀⢠⣏⣽⠀⠀⠀⠀⠀⠀⢤⣀⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣇⠀⢸⣿⣿⣿⣿⢣
⣿⣿⣿⡇⠀⢈⣷⢹⠀⡇⠀⠀⠀⢀⣀⣹⣮⠉⠑⠴⠖⠢⠤⠤⠄⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠀⠤⠤⠤⠒⠒⢈⣉⣥⣖⣀⠀⠀⠀⠀⢀⠀⠀⣸⣇⠀⢸⣿⣿⣿⡟⠘
⣿⣿⣿⡇⢠⣿⣿⢠⢠⣇⠀⠀⠀⠀⠀⠈⢿⢿⡷⣦⣉⠱⢍⣀⡀⠸⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡟⠀⢀⣠⠤⢐⣾⠿⣿⠟⠉⠀⠀⠀⠀⢻⣞⣄⠀⢿⣿⡀⠘⣿⣿⣿⣿⣰
⣿⣿⣿⡇⢸⢸⣿⡼⢸⡿⠁⢀⣤⠤⠖⠒⠲⠾⣿⣦⡍⠓⣄⠈⠉⠉⢿⡄⠀⠀⠀⠀⠀⠀⠀⢀⣾⠋⠉⠁⠀⠖⠉⣡⣮⡷⠖⠒⠲⠦⠤⣠⠄⢻⣿⠀⢸⣿⣇⠀⣿⣿⣿⣿⡁
⣿⣿⣿⣇⣿⣼⡿⣱⣿⣧⠾⠛⠁⠀⠀⠲⠖⠒⠠⣌⡛⢦⡈⠀⡈⠂⠘⣿⠀⠀⠀⠀⠀⠀⢀⣾⠏⠐⠂⡀⣺⣶⢟⣫⠤⠐⠒⠂⠀⠀⠀⠉⠓⢦⣿⣦⣸⣿⣿⡇⣿⣿⣿⣿⣧
⣿⣿⣿⣿⣿⣟⣿⣿⠟⠁⠀⠀⠀⠀⠀⠀⠉⠀⠀⠀⠈⠢⡛⣦⢳⣄⠀⠘⢧⠀⠀⠀⠀⠀⢰⠏⠀⢀⣜⣿⣿⡵⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣿⣝⣿⡇⣿⣿⣿⣿⣿
⣿⣿⣿⣿⡿⣼⡟⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢱⠈⣗⢻⣤⣉⡉⣇⠀⠀⠀⢠⠏⣉⡥⡿⢿⢿⣹⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⣿⢿⣯⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⡇⠀⠀⠀⠀⠀⣀⣠⣤⣤⣤⣤⣤⣀⡀⠀⠀⠂⡌⡇⢳⡀⠉⢹⡉⠉⠉⡟⠉⠀⣼⠁⡇⠆⢀⠀⠀⣀⣤⣤⣤⣤⣤⣄⣀⡀⠀⠀⠀⠀⢀⣿⣿⣿⣿⣿⣿⡿⠋
⠘⢿⣿⡟⢻⣿⣷⣤⣤⣴⣾⣿⣿⣿⠿⠟⠛⠛⠿⠿⣿⣷⣦⣀⠘⠄⢿⡿⢤⠈⢃⡆⣒⠹⢁⣖⡇⠀⠂⢀⣬⣾⣿⡿⠿⠟⠛⠻⠿⣿⣿⣿⣿⣦⣤⣤⣽⣿⣿⢻⣿⣿⠟⣠⡴
⢳⣸⣿⠁⠮⣿⣿⣿⣿⣿⣿⡿⠋⠁⢀⣠⣤⣤⣄⡀⠈⠹⢿⣿⣷⡄⣸⣹⡏⠀⢸⣿⡇⠀⢸⣿⢣⢀⣴⣿⣿⠟⠉⠀⣀⣤⣤⣤⣀⠀⠙⢿⣿⣿⣿⣿⣿⣿⡯⡂⢿⣧⣼⣋⣤
⣝⣿⡟⢀⣹⣿⣿⣿⣿⣿⡿⠁⠀⡰⢿⣿⣿⣿⣿⣿⣦⠀⠈⢿⣿⣿⣾⡟⠀⣀⢼⠟⣿⣄⡀⠹⣷⣿⣿⡿⡇⠀⢀⣾⣿⣿⣿⣿⣿⣷⡄⠀⢹⣿⣿⣿⣿⣿⣿⣁⢸⣿⣟⠟⢳
⢸⣿⠃⢠⢽⣽⢿⣿⣿⣿⡇⠄⠀⣿⣿⣿⡁⠈⣿⣿⣿⡆⠀⢘⣿⣿⡿⠛⠛⢛⣉⡉⣉⡛⠛⠛⢿⣿⣿⡇⠧⠀⢸⣻⣿⣏⠀⣹⣿⣿⡧⠀⢸⣿⣿⣿⣿⢟⡟⠉⠉⣿⣯⠀⣸
⢸⣿⠠⠆⢨⣻⣿⣟⢿⣿⣿⡀⠀⢻⣿⣿⣿⣿⣿⣿⡟⠀⠀⣼⣿⣿⣿⢶⣛⣿⣷⣖⣶⣿⣟⣷⢾⣿⣿⣷⡀⠀⠘⢿⣿⣿⣿⣿⣿⣿⠃⠀⣾⣿⣿⣿⠿⣫⠠⠂⠀⢹⣿⢀⡇
⣿⡏⢰⠀⠀⠙⠶⠶⠾⣿⣿⣷⣄⠀⠉⠛⠻⠟⠛⠉⠀⣠⣾⣿⣿⣿⠟⠛⣉⣩⡀⠀⢀⣨⣉⡛⡿⣿⣿⣿⣷⣄⠀⠈⠙⠛⠿⠟⠋⠁⣠⣾⣿⣿⡿⠷⠾⠟⠁⠀⠀⢸⣿⡾⢠
⣿⣇⢨⣇⠀⠀⠀⠈⡻⠶⢭⣿⣿⣿⣶⣦⣤⣤⣤⣶⣾⣿⣿⢿⣿⡟⡆⣸⣿⡿⠃⠀⠈⠻⣿⣷⠀⠹⣿⢿⣿⣿⣿⣶⣦⣤⣤⣴⣶⣿⣿⣿⡯⠷⣟⠃⠀⠀⠀⢰⡇⢰⣿⠀⡊
⢹⣿⡸⣿⣆⠀⡀⠀⠺⢶⣖⣲⣤⣤⣼⣿⣿⣿⣿⣿⡿⣿⣟⡍⣿⡛⢰⣿⡟⠀⠀⠀⠀⠀⠹⣿⣧⢦⣻⣎⡈⠙⢿⣿⣿⣿⣿⣿⣽⣤⣤⡴⣲⠞⢃⣄⠀⠀⢠⡿⠁⣼⡿⢸⢹
⣷⣿⣿⡷⡉⡻⣿⣿⡆⠀⠀⠈⠉⠁⠀⠀⢋⣉⣠⣶⠿⠟⢉⡼⠓⠁⣾⡟⠀⠀⠀⠀⠀⠀⠀⠹⣿⡄⠉⢿⣌⠻⠷⢦⣬⣉⡙⠁⠀⠁⠉⠉⣤⠔⢉⣿⣿⠟⠋⢀⣼⣿⣷⢿⣸
⠈⠙⠿⣿⣷⡜⣜⣿⣿⢦⣤⣤⣀⣠⣴⣶⠿⠟⠋⠀⠀⠀⠋⠀⠀⢸⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣷⠈⠛⠛⠀⠀⠀⠉⠛⢿⣷⣦⣤⣀⡄⣠⣠⣾⣿⡇⠀⢠⣾⡿⠛⠙⢸⣼
⠀⠀⠀⢻⣿⣿⡄⣿⣿⡻⣯⣿⣿⠟⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠿⣿⣿⡋⠀⣿⣿⢁⣴⣿⣿⠁⠀⠀⣹⢸
⠀⠀⠀⠸⣿⡿⣿⡹⣿⣷⣤⣄⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣤⣾⣿⠟⣼⡿⣿⡏⠀⠀⠀⢸⢻
⠤⣄⣄⡀⢻⣿⠈⢷⣀⠙⣿⣿⣿⣶⣤⣤⣄⣀⣀⣀⣀⣀⣀⣤⣤⣤⣶⣶⣾⣷⣦⣀⣤⣾⣷⣶⣶⣦⣤⣤⣀⣀⣀⣀⣀⣀⣀⣤⣤⣶⣾⣿⣿⠟⣡⡼⠏⣸⣿⢀⣀⣤⣤⣾⣻
⠁⠈⠛⠙⢸⣿⡄⣎⡇⢳⣞⣿⣟⡟⠻⡟⢿⣿⣿⣿⣿⣿⣿⣷⣶⣾⣿⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⢻⡿⢛⢿⣿⡏⡰⢻⡇⣀⣿⡟⠉⢹⣿⡟⠙⠉
⠀⠀⠀⠀⠠⢿⣷⢏⢧⠀⡎⣻⣿⣿⡄⣿⡀⢻⠁⠈⣿⠁⠙⣟⠁⠙⡿⠋⢻⡟⠛⢿⠟⠻⡿⠋⢻⡏⠀⢹⡏⠈⣻⠋⠈⣿⠁⣼⣄⣾⣿⡟⠀⠀⣾⠳⢻⣿⢡⠀⠈⢿⣷⡀⠀
⠀⠀⠀⢠⠇⠸⣿⡘⣏⣇⠸⢳⢿⣿⣿⣿⣧⣸⣧⢠⣿⡇⢸⣿⠀⢰⣧⠀⣸⡇⢠⣿⡄⢠⣧⠀⣸⣇⠀⣸⣷⢠⣿⡇⢰⣿⣼⣿⣿⣿⣿⠃⠀⣸⠃⠀⣾⡿⠈⣆⠀⠈⠻⣿⣦
⠀⢀⣾⠏⠀⠀⣿⣇⢸⣾⠀⡏⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣇⣿⣿⣦⣿⣷⣸⣿⣷⣼⣿⣧⣿⣿⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠀⢀⡿⠀⢰⣿⠇⠀⠘⣷⣄⡀⠈⠙
⢔⡽⠃⠀⠀⢠⢻⣿⠈⡟⢢⢸⣼⣿⣿⣿⣿⣏⣿⠹⣿⢻⣿⢻⣿⢿⣿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⣿⡟⢿⡏⢻⢏⣷⣿⣿⣿⠇⢰⢸⠃⠀⣸⣿⢦⠀⠀⠈⠻⣿⣶⡤
⠀⠀⠀⠀⣰⠏⠈⢿⣧⡸⡸⣟⣇⢹⣿⣿⣿⣿⣿⣶⣧⣠⣯⣀⣿⢘⡏⠘⡟⢻⡟⣿⠋⣿⢹⡏⢘⣇⣸⣇⣸⣅⣸⣷⣾⣿⣿⣿⣿⡿⢀⡿⠀⠀⣴⣿⠇⠘⣷⡀⠀⠀⠈⠙⠻
⠀⠀⣠⣾⡏⠀⠀⠈⢻⣷⡕⢎⢹⣯⡛⢿⣿⣿⣿⣿⣿⡿⠿⣿⣿⣿⣿⣾⣿⣾⣷⣿⣶⣿⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠁⡾⠁⢀⣼⡿⠃⠀⠀⠙⣿⣦⠀⠀⠀⠀
⠀⢞⣿⠏⠀⠀⠀⠀⠀⠹⣿⣝⢆⠹⢇⠀⠉⠛⠿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠟⠋⠁⣠⡾⠁⢠⣾⡿⠁⠀⠀⠀⠀⠹⣿⣷⣦⡀⠀
⠚⠋⠋⠀⠀⠀⠀⠀⠀⠀⢻⣿⣯⡳⡄⠕⠂⠀⠀⠀⠀⠉⠉⠛⠛⠛⠛⠛⠛⠛⠿⠿⠿⠟⠛⠛⠛⠛⠛⠛⠋⠉⠁⠀⠀⠀⠤⠚⠋⡴⣱⣿⢿⠁⠀⠀⠀⠀⠀⠀⢈⡿⠿⣿⣦
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢨⣯⢻⣷⣍⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣾⡿⢻⣇⠀⠀⠀⠀⠀⠀⠀⠩⢒⠀⠀⠉
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⡟⡎⢻⣿⣦⡀⠀⠀⠀⢀⣤⡤⠖⢚⣃⣀⡤⠄⠀⠀⠀⠀⠀⠀⢤⣄⣈⣓⠒⠤⣤⣀⠀⠀⠀⢀⣰⣿⣿⢃⣾⡏⠀⠀⠀⠀⠀⠀⠀⠐⠉⠀⠀⠀
⣍⠉⠛⠿⠷⣶⣶⣶⣶⣟⠯⠅⠸⣌⢿⣻⣿⡟⠓⠛⠋⠁⠒⠉⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠉⠓⠈⠉⠛⠛⢛⣿⣿⣿⣁⠞⢀⠥⣒⣶⣶⣶⣶⠾⠿⠟⠋⢁⣴⡾
⠛⢷⣤⡀⡀⠀⠀⠀⠀⠀⠀⠀⠐⣼⡷⣿⣿⣿⣆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⣿⣿⡿⣷⣟⠀⠐⠃⠀⠀⠀⠀⠀⠠⢒⣠⣾⠟⠁⠀
⠀⠀⢉⡻⣷⣄⠀⠀⠀⠀⠀⠀⠀⠘⢿⣳⣿⣿⣿⣦⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣰⣿⣿⡿⡟⡽⠋⠀⠀⠀⠀⠀⠀⠀⣀⣴⠟⣋⠴⣪⠄⠀
⡄⠀⣠⢌⢷⢟⠻⢷⣦⢤⣀⠀⠀⠀⠀⠙⣿⣿⣮⢿⣷⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⡿⣫⣿⣿⠟⠁⠀⠀⠀⢀⡠⣴⣾⠿⢋⡠⣚⣵⡮⠖⣾⡋
⣇⠀⢈⣵⣶⣭⣛⠀⠙⣛⢾⣿⣖⣦⣀⡀⢘⣿⣿⣧⢻⣿⣆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣾⡿⣱⣿⣿⡋⠀⣀⣤⣶⣾⡿⠞⠋⡠⠖⣥⣾⣧⣅⠀⣠⣿⣿
⣿⣿⡿⠭⠤⢹⣷⢈⡙⠂⠈⠓⠽⣮⠽⣿⠿⣿⣿⡝⣷⡹⣿⣅⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⡟⣽⢯⣾⣿⡿⣿⡿⢁⠋⠁⠀⠀⠁⡀⢸⣟⠀⠬⣿⣿⣿⣿⣿
⣿⣾⣿⣧⣶⣟⣵⢶⣍⠲⢤⣀⠀⠈⠁⠠⠙⠺⣿⡃⠈⢳⡝⠻⢿⣶⣶⣤⣤⣤⣤⣀⣠⣤⣤⣤⣴⣶⣿⠿⢋⡾⠋⢨⣿⠿⠋⠥⠚⠁⠀⢀⣤⠖⣋⣵⢶⣝⣷⣜⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣶⣿⠁⠉⠳⠿⣦⣄⡀⠀⠀⠀⠉⠳⢦⡹⣄⠀⠀⢻⣏⠙⠛⠛⠛⠛⠛⠋⣩⡿⠁⠀⢠⠟⣠⠾⠋⠊⠀⠊⠀⣠⣴⠾⠗⠋⠀⣿⣧⣺⣿⣿⣿⣿⣿⣿⣿⣿
*/
#include <bits/stdc++.h>
using namespace std;
#define fore(i, a, b) for (int i = (a); i <= (b); i++)
#define ford(i, a, b) for (int i = (a); i >= (b); i--)
#define int long long
using vi = vector<int>;
using ii = pair<int, int>;
#define pb emplace_back
#define fi first
#define se second
#define sz(v) ((int)v.size())
#define all(v) v.begin() + 1, v.end()
#define alll(v) v.begin(), v.end()
#define db(x) cerr << "[" << #x << " = " << x << "]"
#define ell cerr << "\n=========================================\n"
#define el cerr << '\n'
#define Unique(v) v.erase(unique(alll(v)), v.end())
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r)
{
assert(l <= r);
return uniform_int_distribution<int> (l, r)(rng);
}
template<int D, typename T> struct Vec : public vector < Vec < D - 1, T >>
{
template<typename... Args> Vec(int n = 0, Args... args) : vector < Vec < D - 1, T >> (n, Vec < D - 1, T > (args...)) {}
};
template<typename T> struct Vec<1, T> : public vector<T>
{
Vec(int n = 0, const T &val = T()) : vector<T>(n, val) {}
};
vi zfunc(const string &s)
{
int n = sz(s);
vi z(n);
int l = 0, r = 0;
fore(i, 1, n - 1)
{
if(i < r) z[i] = min(r - i, z[i - l]);
while(i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
if(i + z[i] > r) l = i, r = i + z[i];
}
return z;
}
const int N = 3005;
vi ev[N];
void ivan()
{
string a, b;
cin >> a >> b;
int n = sz(a), m = sz(b);
vi z, t;
string c;
int ans = 0;
string ra = a, rb = b;
reverse(alll(ra));
reverse(alll(rb));
multiset<int> ms;
int sa = 0, sb = 0;
fore(ite, 0, 1)
{
fore(len, 0, m)
{
ms.clear();
c = a.substr(0, len);
c += b;
z = zfunc(c);
if (len < n) c = a.substr(len, n - len), c += b, t = zfunc(c);
else t.clear();
fore(i, 0, m) ev[i].clear();
fore(i, 0, m - 1)
{
int pos = n - len + i - 1, l1 = 0;
if (i > 0 && pos < sz(t) && pos > 0)
{
ev[i - 1 + t[pos]].pb(i - 1);
ms.emplace(i - 1);
}
for (const auto &x : ev[i - 1]) ms.erase(ms.find(x));
if (sz(ms)) l1 = i - *ms.begin();
int l2 = 0;
if (len + i < sz(z)) l2 = z[len + i];
if (ans < l1 + l2)
{
ans = l1 + l2;
sb = i - l1;
sa = len - l2;
if (ite)
sa = sa + ans - 1, sa = n - sa - 1;
}
}
}
swap(a, ra);
}
cout << ans << '\n' << sa<< ' ' << sb;
cout << '\n';
}
signed main()
{
cin.tie(0)->sync_with_stdio(0);
if (fopen("in", "r")) freopen("in", "r", stdin);
if (fopen(TASKNAME".inp", "r"))
{
freopen(TASKNAME".inp", "r", stdin);
freopen(TASKNAME".out", "w", stdout);
}
int tc = 1;
// cin >> tc;
while (tc--) ivan();
ell, cerr << "Execution Time: " << 1.0 * clock() / CLOCKS_PER_SEC << "s", ell;
return 0;
}
