D. Миша ба сэлгэмлүүдийн нийлбэр

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

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

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

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

$0, 1, ..., (n - 1)$ тоонуудаар үүсэх сэлгэмэлүүдийн толь бичгийн дарааллын дагуу $x$ дэх сэлгэмлийг ($0$-ээс эхлэн дугаарлана) $Perm(x)$ гэе. Харин $Ord(p)$ нь $p$ сэлгэмлийн толь бичгийн эрэмбээрх дугаар нь байг. $0, 1, ..., (n - 1)$ тоонуудаар үүсэх $p$ болон $q$ сэлгэмлүүдийн нийлбэр гэдгээр $Perm(Ord(p) + Ord(q))\ mod\ n!)$ сэлгэмэлийг тодорхойлъё.

Жишээ нь: $Perm(0) = (0, 1, ..., n-2, n-1)$; $Perm(n!-1) = (n-1, n-2, ..., 1, 0)$

Мишад $p$ ба $q$ гэсэн хоёр сэлгэмэл байгаа. Чиний даалгавар бол тэдгээрийн нийлбэрийг олох юм.

Хэрэв $a_{0} = b_{0}, a_{1} = b_{1}, ..., a_{k - 1} = b_{k - 1}, a_{k} < b_{k}$ нөхцлийг хангадаг байхаар $k$ дугаар олддог бол сэлгэмэл $a = (a_{0}, a_{1}, ..., a_{n - 1})$-г сэлгэмэл $b = (b_{0}, b_{1}, ..., b_{n - 1})$-ээс толь бичгийн эрэмбээрээ бага гэж үзнэ.

Оролт

Эхний мөрөнд бүхэл тоо $n$ ($1 ≤ n ≤ 200000$) байрлана.

Хоёр дахь мөрөнд $p$ сэлгэмлийг илэрхийлсэн $0$-ээс $n-1$ хүртэлх ялгаатай $n$ ширхэг бүхэл тоо зайгаар тусгаарлагдан байрлана.

Гурав дахь мөрөнд $q$ сэлгэмлийг илэрхийлсэн $0$-ээс $n-1$ хүртэлх ялгаатай $n$ ширхэг бүхэл тоо зайгаар тусгаарлагдан байрлана.

Гаралт

Өгөгдсөн сэлгэмлүүдийн нийлбэр сэлгэмлийг илэрхийлсэн $0$-ээс $n-1$ хүртэлх ялгаатай $n$ ширхэг бүхэл тоог зайгаар тусгаарлан хэвлэ.

Орчуулсан: Бат-Од

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

Оролт
2
0 1
0 1
Гаралт
0 1
Оролт
2
0 1
1 0
Гаралт
1 0
Оролт
3
1 2 0
2 1 0
Гаралт
1 0 2

Тэмдэглэл

$0$-ээс $1$ хүртэлх тоонуудаар үүсэх сэлгэмэлүүдийн толь бичгийн эрэмбэ нь: $(0, 1), (1, 0)$.

Эхний жишээнд $Ord(p) = 0$ ба $Ord(q) = 0$ тул хариу:

$Perm((0+0)\ mod\ 2) = Perm(0) = (0, 1)$.

Хоёр дахь жишээнд $Ord(p) = 0$ ба $Ord(q) = 1$ тул хариу:

$Perm((0+1)\ mod \ 2) = Perm(1) = (1, 0)$.

$0$-ээс $2$ хүртэлх тоонуудаар үүсэх сэлгэмлүүдийн толь бичгийн эрэмбэ нь: $(0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)$.

Гурав дахь жишээнд $Ord(p) = 3$ ба $Ord(q) = 5$ тул хариу:

$Perm((3 + 5)\ mod\ 6) = Perm(2) = (1, 0, 2)$.

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