Сразу скажу, это единственная задача, которая не вошла в https://codeforces.net/blog/entry/74106, основанный на МОШе, и не зря, ведь там нужно было ифать кучу случаев, и у меня, например, за неё 98 баллов :)