Нэг улс шулуун том замын дагуу байрласан $(n + 1)$ хотоос бүрддэг. Хотуудыг шулуун том замын дагуу тохиох дарааллаар нь $1$-c $n + 1$ хүртэлх дараалласан бүхэл тоонуудаар дугаарлацгаая. Иймээс хотууд том замын $n$ хэсгүүдээр холбогдсон ба $i$-р хэсэг нь $i$ болон $i + 1$ дугаартай хотуудыг холбоно. Том замын хэсэг бүр түүний замын бөглөрөлтэй байх үеийг илэрхийлэх эерэг бүхэл тоон утга $a_{i} > 1$-тай холбоотой.

$x$ хотоос $y$ ($x < y$) хот орохын тулд зарим жолооч нар дараах тактикуудыг ашиглана.

Анх жолооч $x$ хотод байх ба $t$ цаг тэгтэй тэнцүү байна. Жолооч $y$ хотод ирэх хүртлээ дараах үйлдлүүдийг гүйцэтгэнэ:

• хэрвээ одоогийн цаг $t$ нь $a_{x}$-н үржвэр болж байвал $x$ дугаартай том замын хэсэг нь одоо авто замын асуудалтай байгаа ба жолооч одоо байгаа хотдоо нэг хугацааны нэгж хугацаанд үлдэнэ (бид $t = t + 1$ болгоно).
• хэрвээ одоогийн цаг $t$ нь $a_{x}$-н үржвэр болохгүй байвал $x$ дугаартай том замын хэсэг нь одоо ямар ч түгжрэлгүй байгаа ба энэ нь жолооч $x + 1$ (бид $t = t + 1$ ба $x = x + 1$ болгоно) хотруу хугацааны нэг нэгжийг ашиглан очих шалтгаан юм.

Та шинэ авто замын удирдлагын систем хөгжүүлж байгаа. Та хоёр төрлийн дараалласан $q$ даалгаварыг гүйцэтгэнэ:

1. $x$ хотоос $y$ ($x < y$) хот хүрэхэд $t$ цагийн эцсийн утгыг тодорхойлох ба бид дээр тодорхойлсон тактикуудыг хэрэгжүүлнэ гэж үз.
2. $x$ дугаартай хэсэгт байгаа замын түгжрэлийн үеийг $y$ утгаар соль ($a_{x} = y$ болго).

Дээр өгөгдсөн даалгаваруудыг үр дүнтэйгээр биелүүлэх кодыг бич.

Оролт

Оролтын эхний мөрөнд нэг ширхэг бүхэл тоон утга $n$ ($1 ≤ n ≤ 10^{5}$) байх ба $n + 1$ хотуудыг холбох том замын хэсгүүдийн тоо.

Хоёр дахь мөрөнд $n$ бүхэл тоон утга $a_{1}, a_{2}, ..., a_{n}$ ($2 ≤ a_{i} ≤ 6$) байх ба том замын хэсгүүд дээрх замын түгжрэлийн үе.

Дараагийн мөрөнд нэг ширхэг бүхэл тоон утга $q$ ($1 ≤ q ≤ 10^{5}$) байх ба гүйцэтгэх даалгаваруудын тоо.

Дараагийн $q$ мөрөнд даалгаваруудын тайлбарууд $c$, $x$, $y$ ($c$ -- даалгаварын төрөл) форматтай байна.

Хэрвээ $c$ нь '$A$' тэмдэгт байвал таны ажил эхний төрлийн даалгаварыг гүйцэтгэх байна. Энэ тохиолдолд дараах хязгаарлалтууд байна: $1 ≤ x < y ≤ n + 1$.

Хэрвээ $c$ нь '$C$' тэмдэгт байвал таны ажил хоёрдугаар төрлийн даалгаварыг гүйцэтгэх байна. Энэ тохиолдолд дараах хязгаарлалтууд байна: $1 ≤ x ≤ n$, $2 ≤ y ≤ 6$..

Гаралт

Эхний төрлийн даалгавар бүрийн хувьд $x$ хотоос $y$ хотод очиход $t$ цагийн эцсийн утгыг илэрхийлэх нэг ширхэг бүхэл тоон утгыг хэвлэ. Даалгаваруудыг оролтонд өгөгдсөн дарааллаар гүйцэтгэ.