template <typename It, typename OutputIt>
OutputIt sideways_merge(It first1, It last1, It first2, It last2, OutputIt out) {
    --last2;
    --first2;
    while (first1 != last1 || last2 != first2) {
        if (first1 == last1) {
            *out++ = *last2--;
        } else if (last2 == first2) {
            *out++ = *first1++;
        } else {
            *out++ = (*first1 < *last2 ? *first1++ : *last2--);
        }
    }
    return out;

}