D. Баг зохион байгуулах

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Бэрландын Улсын Их Сургуулийн Програмын Олимпиадын Бэлтгэлийн Төвийн хувийн бэлтгэлийн хугацаа сая дууслаа. Энэхүү бэлтгэлийн хугацааны үр дүнгээр удахгүй эхлэх багийн бэлтгэлийн улиралд оролцох багуудыг бүрдүүлэв. Баг бүр гурван хүнтэй байна. Энэ төвийн бүх сурагчид $1$-ээс $3n$ дугаартай, бүх баг $1$-ээс $n$ дугаартай. Оюутнуудыг багуудад хуваахдаа дараах байдлаар гүйцэтгэнэ: баггүй байгаа хүмүүсээс хамгийн их оноотойг нь сонгоод (шинэ багийн ахлагчаар), тэр хүн өөрийн эрэмбэлсэн жагсаалтын дагуу багийн үлдсэн хоёр гишүүнээ сонгоно. Хүн бүрийн хувьд эрэмбэлсэн жагсаалт нь энэ төвд суралцаж байгаа өөрөөс нь бусад $3n - 1$ сурагчдын сэлгэмэл байна.

Танд энэхүү хувийн бэлтгэлийн үр дүн болох $1$-ээс $3n$ тоонуудын сэлгэмэл өгөгдөх бөгөөд $i$ дэх тоо нь $i$-р байр эзэлсэн сурагчийн дугаар юм. Байр хувааж эзэлсэн хоёр сурагч байхгүй. Танд бас аль хэдийн багуудад хуваагдсан зохиын байгуулалт өгөгдсөн. Таны даалгавар бол $k$ дугаартай хүүхдийн эрэмбэлсэн жагсаалтыг тодорхойлох юм. Хэд хэдэн хариутай бол толь зүйн дарааллаар хамгийн багыг нь сонго.

Оролт

Эхний мөр багуудын тоо болох $n$ ($1 ≤ n ≤ 10^5$) бүхэл тоог агуулна. Хоёрдахь мөр хувийн бэлтгэлийн дүн болох $3n$ ширхэг зайгаар тусгаарлагдсан $1$-ээс $3n$ хүртэлт тоонуудыг агуулна. Ямар ч байсан сурагч бүх яг нэг байр эзэлсэн байна.

Дараагийн $n$ мөрөнд мөр бүрт багийн гишүүд болох $1$-ээс $3n$-ийн хоорондох гурван тоо өгөгднө. Багийн гишүүд дотроо ямар ч байдлаар жагсч болох боловч багууд байгуулагдсан дарааллаараа жагсна. Энэ зохион байгуулсан хуваарилалт нь баталгаатай зөв, сурагч бүр яг нэг багт орох бөгөөд багууд дээр тодорхойлсон аргыг дагуу байгуулагдна.

Сүүлийн мөр жагсаалтыг нь олох ёстой сурагчийн дугаар болох $k$ ($1 ≤ k ≤ 3n$) бүхэл тоог агуулна.

Гаралт

$k$ дугаартай сурагчийн боломжит эрэмбэлсэн жагсаалтуудын толь зүйн дарааллаар хамгийн бага нь байх $3n - 1$ ширхэг бүхэл тоог хэвлэ.

Толь зүйн харьцуулалт нь орчин үеийн програмчлалын хэлнүүдийн $<$ стандарт үйлдлээр гүйцэтгэгднэ. $a$ жагсаалт $b$ жагсаалтаас толь зүйн дарааллаар бага байна гэж, $a_i < b_i$ ба $j$ ($1 ≤ j < i$) бүрийн хувьд $a_j = b_j$ байх $i$ ($1 ≤ i ≤ 3n$) тоо олдохыг хэлнэ. $1$ $9$ $10$ жагсаалт нь $1$ $10$ $9$ жагсаалтаас толь зүйн дарааллаар бага. Ер нь бол жагсаалтын харьцуулаль тэмдэгт мөрийн харьцуулалтаас ялгаатай юм.

Орчуулсан: Sugardorj

Жишээ тэстүүд

Оролт
3
5 4 1 2 6 3 7 8 9
5 6 2
9 3 4
1 7 8
4
Гаралт
2 3 5 6 9 1 7 8 
Оролт
3
5 4 1 2 6 3 7 8 9
5 6 2
9 3 4
1 7 8
8
Гаралт
1 2 3 4 5 6 7 9 
Оролт
2
4 1 3 2 5 6
4 6 5
1 2 3
4
Гаралт
5 6 1 2 3 
Сэтгэгдлүүдийг ачааллаж байна...