import zlib,base64;exec(zlib.decompress(base64.b85decode('ZIQuFgfI|>?|q6t>tR8`$d!bv;k;|Yfe?eSxYK2U6joo~=}?dmPfcgO&U`=Q5ej6u)k8qt6oI0nTDPOF@W?s-(QBxq@gk^z>gPhOM%Pd9LrTjA)>LlyuEdYt>|HAnddiR}advhY@>y0?UzBKW5aW=-BgP|=cb(0NAAI7CrC+!tUZ*mGMqy<(y67xxw;Z4_rDVkwiceD$O4%UAu?2?}tP93j'),-15))