E. Хэсгүүдийн аялал

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

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

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

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

Нэгэн клуб өөрсдийн гишүүдтэйгээ аялахыг хүсжээ. Уг үйл ажиллагааг илүү сайн зохион байгуулахын тулд клубийн удирдлагууд гишүүдээ хэд хэдэн хэсгүүдэд хуваахаар шийджээ.

Клубийн гишүүн $i$ нь $r_{i}$ үүрэг хариуцлагатай ба $a_{i}$ настай байна. Хэсэг гэдэг нь клубийн гишүүдийн хоосон биш дэд олонлог бөгөөд нэг гишүүнээ хэсгийн ахлагч болгосон байна. Хэсгийн ахлагч нь уг хэсгийн хамгийн их үүрэг хариуцлагатай (түүний үүрэг хариуцлага нь хэсгийн бусад аль ч гишүүний үүрэг хариуцлагаас багагүй байна) гишүүн байх ёстой ба түүний нас болон уг хэсгийн бусад аль ч гишүүний насны абсолют зөрүү нь $k$-аас хэтрэхгүй байна.

Клубийн зарим гишүүд нь найзууд ба нэг ижил хэсэгт байхыг хүснэ. Тэд мөн тэдгээрийн хамтдаа байх хэсэг нь аль болох том байхыг хүсэх юм. Одоо та "клубийн гишүүн $x$ болон клубийн гишүүн $y$-ыг агуулах хэсгийн хамгийн том хэмжээ нь хэд вэ?" гэсэн хэлбэртэй асуултуудын цуваанд хариулах программ бичих юм. $x$ эсвэл $y$ нь хэсгийн ахлагч байх боломжтой.

Оролт

Эхний мөрөнд клубийн гишүүдийн тоо болон нэг хэсгийн насны хязгаарлалт болох нэг 2 бүхэл тоо $n$ болон $k$ ($2 ≤ n ≤ 10^{5}, 0 ≤ k ≤ 10^{9}$) өгөгдөнө.

Дараагийн мөрөнд зайгаар тусгаарлагдсан бүхэл тоонууд $r_{1}, r_{2}, ..., r_{n}$ ($1 ≤ r_{i} ≤ 10^{9}$) өгөгдөх ба $r_{i}$ нь $i$-дахь клубийн гишүүний үүрэг хариуцлагыг илэрхийлнэ. Мөн ижлээр $a_{1}, a_{2}, ..., a_{n}$ ($1 ≤ a_{i} ≤ 10^{9}$) бүхэл тоонууд нь 3-дахь мөрөнд өгөгдөх ба эдгээр нь $i$-дахь клубийн гишүүний насыг илэрхийлнэ.

Дараагийн мөрөнд таны хариулах ёстой асуултуудын тоог илэрхийлэх бүхэл тоо $q$ ($1 ≤ q ≤ 10^{5}$) өгөгдөнө. Дараагийн $q$ мөрөнд асуултуудыг дүрсэлнэ. Мөр болгонд зайгаар тусгаарлагдсан 2 бүхэл тоо $x_{i}$ болон $y_{i}$ ($1 ≤ x_{i}, y_{i} ≤ n, x_{i} ≠ y_{i}$) өгөгдөх ба эдгээр нь нэг хэсэгт байх ёстой клубуудын гишүүдийн дугааруудыг илэрхийлнэ.

Гаралт

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

Орчуулсан: Баатархүү

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

Оролт
5 1
1 5 4 1 2
4 4 3 2 2
4
5 3
2 3
2 5
4 1
Гаралт
4
3
-1
4

Тэмдэглэл

Эхний асуултын 3 болон 5 дугаартай гишүүдтэй хамгийн том хэсэг нь ${1, 3, 4, 5}$ байх ба энд 3 дугаартай гишүүн нь ахлагч байна.

2-дахь асуултын 2 дугаартай гишүүн нь ахлагч байх ёстой ба хамгийн том хэсэг нь ${1, 2, 3}$ байна.

3-дахь асуултын хэсгийн ахлагч нь заавал 3-н настай байх ба иймд цорын ганц боломжит ахлагч нь 3 дугаартай гишүүн бөгөөд түүний үүрэг хариуцлага нь 2 дугаартай гишүүн үүрэг хариуцлагаас бага байна. Иймд уг хэсэг байгуулах нь боломжгүй байна.

4-дэх асуултын хэсэг нь эхний асуултын хэсэгтэй ижил байх юм.

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