C. Аняа ба Ухаалаг утас

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

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

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

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

Аняа Бердройд үйлдлийн системтэй шинэ ухаалаг утас худалдаж авчээ. Ухаалаг утасны цэс яг $n$ ширхэг аппликейшнтэй. Аппликейшн болгон өөрийн гэсэн таних тэмдэгтэй. Таних тэмдэгнүүд ялгаатай хуудаснуудад байрладаг бөгөөд нэг хуудас $k$ ширхэг таних тэмдэг агуулдаг. Эхний таних тэмдэгнээс эхлэн $k$ дахь таних тэмдэг хүртэл тэмдэгнүүд эхний хуудсанд, $(k + 1)$ дахиас эхлэн $2k$ дахь хүртэл таних тэмдэгнүүд 2 дахь хуудсанд гэх мэт үргэлжилнэ (сүүлийн хуудасны зарим хэсэг хоосон байж болно).

Эхлээд ухаалаг утасны цэс 1 дэхь хуудсыг харуулдаг. $t$ дэхь хуудсан дээр байгаа таних тэмдэгтэй аппликейшныг ажиллуулахын тулд, Аняа дараах үйлдлүүдийг хийх шаардлагатай: эхлээд $t$ хуудас уруу очихын тулд $t - 1$ ширхэг үйлдэл хийнэ, дараа нь дахин нэг үйлдэл хийнэ -- ажиллуулах гэж буй аппликейшний таних тэмдэг дээр яг нэг удаа дарна.

Аппликейшн ажиллаж эхэлсний дараа, утас эхний хуудас уруу буцна. Тиймээс дараагийн аппликейшнийг ажиллуулахын тулд дахин эхний хуудаснаас эхлэх юм.

Бүх аппликейшнүүд $1$-ээс $n$ хүртэл дугаарлагдсан. Бид анхны цэсэнд байрлаж байсан аппликейшнүүдийн дарааллыг мэднэ, гэвч энэ дараалал нь үйлдлийн системийг хэрэглэх болгонд өөрчлөгддөг. Бердройд нь ухаалаг систем, тиймээс их хэрэглэгдсэн аппликейшний байрлал урагшилдаг. Өөрөөр хэлбэл, аппликейшныг ажиллуулсны дараа Бердройд үйлдлийн систем нь ажиллуулсан аппликейшний таних тэмдэгийг үүний зүүн талын аппликейшний таних тэмдэгний байрлалтай солидог. Ажилласан аппликейшний таних тэмдэг нь тухайн хуудасны хамгийн эхэнд байрлаж байвал өмнөх хуудасны хамгийн сүүлийн аппликейшний таних тэмдэгтэй байраа солино. Байрлал өөрчлөгдөхгүй байх ганц нөхцөл нь хамгийн эхэнд байрлаж буй аппликейшнийг ажиллуулах үед л байрлал өөрчлөгдөхгүй.

Аняа ажиллуулах аппликейшнийхээ дарааллын төлөвлөгөөг гаргажээ. Төлөвлөгөөг гүйцэтгэхийн тулд хэдэн үйлдэл хийх шаардлагатай вэ?

Нэг аппликейшн нэгээс олон удаа ажиллах боломжтойг анхаарна уу.

Оролт

Эхний мөрөнд 3-н тоонууд $n, m, k$ ($1 ≤ n, m, k ≤ 10^{5}$) өгөгдөнө. Эдгээр нь Аняагийн утсанд байгаа аппликейшний тоо, төлөвлөгөөнд байгаа ажиллах аппликейшний тоо, нэг хуудсанд байрлах таних тэмдэгний тоо.

Дараагийн мөр $n$ ширхэг бүхэл тоонууд $a_{1}, a_{2}, ..., a_{n}$ агуулна. Эдгээр нь таних тэмдэгнүүдийн цэсэнд байрлах анхны дараалал зүүнээс баруун уруу өгөгдсөн хэлбэр юм (эхнийхээс сүүлийнх хүртэл). Энд $a_{i}$ нь цэсэнд анх $i$ дахь байрлал дээр байгаа аппликейшний ID. $a_{i}$-үүдэд $1$-ээс $n$-ийн хоорондох бүхэл тоо болгон нэг удаа орсон байна.

3 дахь мөрөнд $m$ ширхэг бүхэл тоонууд $b_{1}, b_{2}, ..., b_{m}(1 ≤ b_{i} ≤ n)$ өгөгдөнө. Эдгээр нь төлөвлөгөөний ажиллуулах дарааллын ID-нууд болно. Нэг аппликейшн нэгээс олон удаа ажиллах боломжтой.

Гаралт

Аняа төлөвлөгөөний дагуу бүх аппликейшнийг ажиллуулахын тулд нийт хэдэн үйлдэл хийх шаардлагатайг олж нэг тоогоор хэвлэнэ үү.

Орчуулсан: Энхлут

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

Оролт
8 3 3
1 2 3 4 5 6 7 8
7 8 1
Гаралт
7
Оролт
5 4 2
3 1 5 2 4
4 4 4 4
Гаралт
8

Тэмдэглэл

Эхний тестэнд анхны байрлал $(123)(456)(78)$ байжээ. Энэ нь эхний хуудас $1, 2, 3$, 2 дахь хуудас $4, 5, 6$, 3 дахь хуудас $7, 8$ таних тэмдэгнүүд агуулж байна гэсэн үг.

Аппликейшн $7$ ажилласаны дараа, шинэ байрлал нь $(123)(457)(68)$ болно. Үүнийг ажиллуулахын тулд Аняа $3$-н үйлдэл хийнэ.

Аппликейшн $8$ ажилласаны дараа, шинэ байрлал нь $(123)(457)(86)$ болно. Үүнийг ажиллуулахын тулд Аняа $3$-н үйлдэл хийнэ.

Аппликейшн $1$ ажилласаны дараа, цэсэн дахь байрлал өөрчлөгдөхгүй. Үүнийг ажиллуулахын тулд Аняа $1$ үйлдэл хийнэ.

Ингээд Аняа нийт $7$ ширхэг үйлдэл хийнэ.

Сэтгэгдлүүдийг ачааллаж байна...