DZY гэрийнхээ ойролцоо $2^{m}$ арал эзэмшдэг ба эдгээр нь $1$-с $2^{m}$ хүртэл дугаарлагдсан. Тэр арлуудыг холбосон гүүр барих дуртай. Түүний барьсан гүүр бүрийг алхаж гарахад нэг өдрийн хугацаа шаардана.

DZY гүүр барих хачирхалтай дүрэмтэй. $u, v (u ≠ v)$ хос арал бүрийн хувьд тэр тэдгээрийг холбосон ялгаатай $2^{k}$ гүүр барьсан ба энд ($a|b$ нь $b$ тоо $a$-д хуваагддаг гэсэн үг). Гүүрүүд хос чиглэлтэй.

Мөн DZY өөрийн гэрийг арлуудтай холбосон хэдэн гүүр барьсан. Тухайлбал түүний гэрээс $i$-р арал хүртэл ялгаатай $a_{i}$ гүүр байгаа. Эдгээр нь нэг чиглэлтэй гүүр ба тэр гэрээ орхисоны дараа хэзээ ч эргэж ирэхгүй.

DZY үзэсгэлэнтэй газруудыг тойрч үзэхээр арлуудруугаа явахаар шийдсэн. Эхлээд тэр гэртээ байх ба түүний гэртэй холбогдсон нэг гүүрээр нэг арал дээр очно. Үүний дараа тэр арлууд дээр $t$ өдрийг өнгөрүүлнэ. Өдөр бүр тэр уг арал дээр үлдэж амрах эсвэл өөр аралруу гүүрээр дамжин явахаа сонгож чадна. Арал дээр нэгээс олон өдөр амарч болно. Нэг гүүрээр хэдэн удаа ч давж болно.

Яг $i$-р өдрийн дараа DZY $i$-р арал дээр байна гэж бодьё. $i$-р өдрийн дараа DZY $i$-р арал дээр хүрэх замуудын тоог $ans[i]$ гэе. Таны ажил бол $i$ бүрийн хувьд $ans[i]$ тоог тооцоолоод $1051131$ тоонд хуваагаад үлдэгдлийг авах юм.

Оролт

Маш их хэмжээтэй оролтоос сэргийлж бид $a$ массивыг үүсгэх дараах аргыг хэрэглэнэ. Танд массивын эхний $s$ элемент өгөгдөнө: $a_{1}, a_{2}, ..., a_{s}$. Бусад бүх элементүүд томьёогоор тооцоологдох ёстой: $a_{i} = (101*a_{i - s} + 10007) mod 1051131$ $(s < i ≤ 2^{m})$.

Эхний мөрөнд гурван бүхэл тоон утга $m, t, s$ $(1 ≤ m ≤ 25; 1 ≤ t ≤ 10^{18}; 1 ≤ s ≤ min(2^{m}, 10^{5}))$ байна.

Хоёр дахь мөрөнд $s$ бүхэл тоон утга $a_{1}, a_{2}, ..., a_{s} (1 ≤ a_{i} ≤ 10^{6})$ байна.

Гаралт

Маш их хэмжээтэй гаралтаас сэргийлж бүх $i$-н хувьд хариултуудыг $1051131$ тоонд хуваагаад үлдэгдлүүдийн xor-нийлбэрийг хэвлэнэ $(1 ≤ i ≤ 2^{m})$. Өөрөөр $(ans[1] mod 1051131) xor (ans[2] mod 1051131) xor... xor (ans[n] mod 1051131)$.

Эхний жишээн дээр $ans = [6, 7, 6, 6]$.

Хэрвээ тэр нэг өдрийн дараа 1-р арал дээр байхыг үсвэл түүнд ялгаатай зургаан зам байна:

1. гэр --> 1 -(үлдэх)-> 1
2. гэр --> 2 --> 1
3. гэр --> 3 --> 1
4. гэр --> 3 --> 1 (1 ба 3-н хооронд хоёр ялгаатай гүүр байгаа)
5. гэр --> 4 --> 1
6. гэр --> 4 --> 1 (гэр ба 4-н хооронд хоёр ялгаатай гүүр байгаа)

Хоёр дахь жишээн дээр $(a_{1}, a_{2}, a_{3}, a_{4}, a_{5}, a_{6}, a_{7}, a_{8}) = (389094, 705719, 547193, 653800, 947499, 17024, 416654, 861849)$, $ans = [235771, 712729, 433182, 745954, 139255, 935785, 620229, 644335]$.