E. Төвөгтэй нууц үг

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

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

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

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

"Оросын програмчлалын аварга" шалгаруулах тэмцээний бодлогуудыг зохиож байх үед нууцлалыг хамгаалахын тулд нууц үгээр нууцалж хамгаалжээ.

Нууц үгээ сонгохын тулд тэмцээн зохион байгуулагчид $n$ баганатай, төгсгөлгүй олон мөртэй хүснэгт зохиох хэрэгтэй. Хүснэгтийг байгуулахдаа эхний мөр бэхлэгдсэн байх ба бусад нь дараах дүрмээр үүснэ:

$i$ дэх мөрийн $p$ дэх нүдэнд $a[i - 1][1...p]$ нүднүүдэд $a[i - 1][p]$ нүдний утга хэдэн удаа бичигдсэн байгааг бичих юм.

Нууцлалын түвшинг баталгаажуулахын тулд зохион байгуулагчид дараах үйлдлийг гүйцэтгэнэ:

  • $a[1][p]$ тоог $v$ тоогоор солин хүснэгтийг дахин байгуулах.
  • Шинэ нууц үг болох $a[x][y]$ тоог олох.

Энэ бүх алхмыг гараараа хийх хэтэрхий нүсэр тул зохион байгуулагчид чамаас тусламж хүсжээ. Зохион байгуулагчдын хүсэлтэнд хариу өгөх програм зохионо уу.

Оролт

Эхний мөрөнд хүснэгтийн баганын тоо болох $n$ ($1 ≤ n ≤ 100000$) байна. Хоёр дахь мөрөнд хүснэгтийн эхний мөрөнд байрлах тоонууд болох $n$ ширхэг бүхэл тоо байх ба тэдгээр нь $1$-ээс ихгүй $10^{9}$-ээс багагүй тоонууд байна.

Гурав дахь мөрөнд хүсэлтийн тоо болох $m$ ($1 ≤ m ≤ 100000$) байна.

Дараачийн мөр бүрт хүсэлтийн тайлбар байх ба тус бүр гурван бүхэл тооноос бүрдсэн дараах хоёр төрлийн хүсэлт байна:

  • Эхний тоо нь $1$ ба үлдсэн хоёр тоо нь $v$, $p$ ($1 ≤ v ≤ 10^{9}$; $1 ≤ p ≤ n$) байг. Тэгвэл чи хүснэгтийн эхний мөрийн $p$ дэх нүдэнд $v$ утгыг тавих ёстой.
  • Эхний тоо нь $2$ ба үлдсэн хоёр тоо нь $x$, $y$ ($1 ≤ x ≤ 10^{5}$; $1 ≤ y ≤ n$) байг. Тэгвэл хүснэгтийн $x$ дүгээр мөрийн $y$ дэх нүдэнд байгаа тоог хэвлэ.

Гаралт

Хоёрдугаар төрлийн хүсэлт бүрийн хариуг дарааллаар нь нэг нэг мөрөнд хэвлэ.

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

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

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