B. Алдаа засах систем

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

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

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

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

Форд Прэфект алчуур хийдэг нэгэн жижигхэн компанид вэб хөгжүүлэгчээр ажилд оржээ. Түүний одоогоор хүлээж аваад байгаа ажлын даалгавар бол компаний вэб сайтад зориулж хайлтын систем хийх явдал байв. Системийн хөгжүүлэлтийн явцад тэр адилхан урттай $S$ ба $T$ тэмдэгт мөрийг харьцуулах дэд програм бичих шаардлагатай болжээ. Интернетээр хэсэг хайсны эцэст тэр ижил урттай $S$ ба $T$ тэмдэгт мөрүүдийн хоорондох Хаммингийн зай буюу $S$ ба $T$ тэмдэгт мөрүүдийн ялгаатай тэмдэгтүүдийн тооны тухай мэджээ. Жишээлбэл, "permanent" ба "pergament" үгсийн хоорондох Хаммингийн зай нь $2$ буюу энэ үгс нь $4$ болон $6$ дахь үсгүүдээрээ ялгаатай байна.

Түүнээс гадна тэрээр уг мэдээллийг хайж байхдаа орчин үеийн хайлтын системүүд хайлтын чанарыг сайжруулахын тулд хүсэлт дэх алдааг засдаг маш хүчирхэг механизмтэй байдаг талаар мөн мэдэж авчээ. Форд хүмүүсийн зуршлийн талаар тийм ч сайн мэддэггүй тул хүсэлт дэх хамгийн нийтлэг алдаа бол тэмдэгт мөрийн дурын $2$ үсгийг (зэргэлдээ байх албагүй) сольж бичих явдал юм гэж үзсэн байна. Тиймээс одоо тэр $S$ тэмдэгт мөрийн аль $2$ үсгийг солих хэрэгтэйг тодорхойлох функц бичихийг хүсэх болов. Ингэснээр $T$ тэмдэгт мөр болон шинэ $S$ тэмдэгт мөрийн хоорондох Хаммингийн зай боломжоороо багасах эсвэл уг үсэг сэлгэлт нь тэмдэгт мөрүүдийн Хаммингийн зайг багасгахгүй гэдгийг тодорхойлох юм.

Түүнд туслаарай!

Оролт

Эхний мөр нь $S$ ба $T$ тэмдэгт мөрүүдийн уртыг харуулах $n$ ($1≤n≤200 000$) бүхэл тоог агуулна.

Хоёр дахь мөр нь $S$ тэмдэгт мөрийг агуулна.

Гурав дахь мөр нь $T$ тэмдэгт мөрийг агуулна.

Дээрх хоёр мөр нь зөвхөн Латин жижиг үсгүүдийг агуулна.

Гаралт

Эхний мөрөнд $S$ дэх үсгүүдээс хоёрыг нь солиход үүсэх $S$ ба $T$ тэмдэгт мөрүүдийн хоорондох хамгийн боломжит бага Хаммингийн зайг харуулах $x$ тоог хэвлээрэй.

Хоёр дахь мөрөнд хэрэв $i$ ба $j$ байрлал дахь үсгүүдийг сольсноор боломжит хамгийн бага зай гарах бол $i$ ба $j$ ($1≤i, j≤n$, $i≠j$) дугааруудын аль нэгийг, эсвэл хэрэв тэмдэгтүүдийг солих шаардлагагүй бол "-1 -1" гэж хэвлээрэй.

Хэрэв олон зөв хариу байвал аль нэгийг нь хэвлээрэй.

Орчуулсан: Солонго

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

Оролт
9
pergament
permanent
Гаралт
1
4 6
Оролт
6
wookie
cookie
Гаралт
1
-1 -1
Оролт
4
petr
egor
Гаралт
2
1 2
Оролт
6
double
bundle
Гаралт
2
4 1

Тэмдэглэл

Хоёр дахь жишээнд $i=2$, $j=3$ гэж хэвлэж бас болно.

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