아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Шкафы

시간 제한2초메모리 제한1024 MB

요약
마주 보는 두 벽장에서, 한쪽에서 고른 서랍이 다른 쪽에서 고른 서랍을 가리지 않도록 가장 많은 서랍을 고른다.
난이도

보통10점 중 7점

유형
정렬, 그리디, 투 포인터
정답자
아직 제출이 없습니다

문제

Региональное отделение одного крупного банка заказало два несгораемых шкафа для хранения личных дел своих клиентов. Каждый шкаф имеет несколько ящиков различной высоты, при просмотре снизу вверх ящики в первом шкафу имеют высоту a_1,a_2,…,a_ma\_1, a\_2, \ldots, a\_m, а ящики во втором шкафу --- высоту b_1,b_2,…,b_nb\_1, b\_2, \ldots, b\_n. 

Шкафы были установлены в узкой нише в стене лицевой стороной друг к другу, поэтому оказалось, что выдвинуть одновременно два ящика, находящиеся напротив друг друга, невозможно. Сотрудники банка постоянно обращаются к личным делам клиентов, поэтому им удобнее держать ящики открытыми в течение рабочего дня. Поскольку пока клиентов у банка немного, использовать все ящики не обязательно. Решено было использовать такое множество ящиков, чтобы их все можно было выдвинуть одновременно и они не мешали друг другу. Чтобы максимально систематизировать работу, необходимо использовать как можно больше ящиков.

Помогите сотрудникам банка выбрать, какие ящики следует использовать.

입력

Первая строка входного файла содержит два целых числа: mm и nn --- количество ящиков в первом и во втором шкафу, соответственно (1≤m,n≤100,0001 \le m, n \le 100\\,000). Вторая строка содержит mm целых чисел: a_1,a_2,…,a_ma\_1, a\_2, \ldots, a\_m --- высоты ящиков в первом шкафу. Третья строка содержит nn целых чисел: b_1,b_2,…,b_nb\_1, b\_2, \ldots, b\_n --- высоты ящиков во втором шкафу. Высоты ящиков положительные и не превышают 10910^9.

출력

На первой строке входного файла выведите два числа kk и ll --- количество ящиков, которые следует использовать в первом и втором шкафу, соответственно. Сумму k+lk+l вам следует максимизировать. На второй строке выведите kk целых чисел --- номера ящиков в первом шкафу, которые следует использовать. На третьей строке выведите ll целых чисел --- номера ящиков во втором шкафу, которые следует использовать. Если оптимальных решений несколько, выведите любое.

예제1

  1. 예제 1

    입력
    5 5
    1 2 3 4 5
    6 4 3 2 1
    
    예상 출력
    3 4
    1 2 3
    2 3 4 5