Мұнда бір қызықты аңыз бар деп елестетіңіз.

Сізге өлшемі \(n\) болатын \(a\) массиві берілген, және осы массивке қатысты \(q\) операцияны орындау қажет. Операциялар үш түрлі болуы мүмкін:

• \(1\) \(l\) \(r\) — \([l, r]\) аралығындағы барлық элементтерді олардың квадраттарына ауыстыру керек, яғни әрбір \(l \le i \le r\) үшін \(a_i := a_i^2\).

• \(2\) \(l\) \(r\) — \([l, r]\) аралығындағы барлық элементтердің қосындысын табу керек, яғни \(\sum\limits_{i=l}^r a_i\). Ұзақ арифметикалық есептеулерден құтылу үшін қосындыны \(998\,244\,353\) модулі бойынша табу керек.

• \(3\) \(i\) \(x\) — \(i\) позициясындағы элементті жаңа \(x\) мәніне ауыстыру керек, яғни \(a_i := x\).

Барлық сұраныстарды орындаңыз және әрбір екінші типтегі сұранысқа жауап беріңіз.

Енгізу

Бірінші жолда бір бүтін сан \(n\) (\(1 \le n \le 150\,000\)) — массив элементтерінің саны.

Екінші жолда массивтің өзі \(a\) беріледі (\(0 \le a_i < 998\,244\,353\)).

Үшінші жолда бір бүтін сан \(q\) (\(1 \le q \le 150\,000\)) — операциялар саны.

Келесі \(q\) жолдың әрқайсысында операция сипаттамасы беріледі:

• \(1\) \(l\) \(r\) (\(1 \le l \le r \le n\))

• \(2\) \(l\) \(r\) (\(1 \le l \le r \le n\))

• \(3\) \(i\) \(x\) (\(1 \le i \le n\), \(0 \le x < 998\,244\,353\))

Шығару

Әрбір екінші типтегі сұранысқа - \([l, r]\) аралығындағы элементтердің қосындысының \(998\,244\,353\) модулі бойынша қалдығын шығарыңыз.

Бағалау жүйесі

Мысалдар

Енгізу 1

6
4 6 1 5 1 1
6
2 6 6
1 2 6
1 3 4
3 6 3
2 1 2
2 2 6

Жауап 1

1
40
666