Ұзындығы $n$ болатын $a$ массиві бар, мұндағы $i$-ші сан $a_i$-ге тең. Сонымен қатар, әр санның ұпайы бар, және $i$-ші санның ұпайы $c_i$-ге тең. Алиса мен Боб кезектесіп жүреді, ойынды Алиса бірінші бастайды.
Ағымдағы раундта ойыншы алдымен $a$ массивін $b$ массивіне көшіреді және $b$ массивін кездейсоқ араластыру үшін кездейсоқ араластыру программасын іске қосады. Нақтырақ айтқанда, кездейсоқ араластыру программасы бірдей ықтималдықпен $b$ массивінің алмастыруларының бірін таңдап, бастапқы $b$ массивін сонымен алмастырады. Ағымдағы $a$ массивінің ұзындығы $m$ болсын делік, сонда ойыншы $0 \le k \le m$ және $a[1 \dots k] = b[1 \dots k]$ болатындай $k$ бүтін санын таңдап, содан кейін $a[1 \dots k]$ бөлігін (яғни $a$ массивінің ұзындығы $k$ болатын префиксін) өшіріп, өшірілген сандардың ұпайын ала алады. Ойын $a$ массиві босаған кезде аяқталады.
Бүкіл процесс барысында $a$ массиві мен оның ұпайлар массиві $c$ араластырылмайтынына, тек олардың префикстері ғана өшірілетініне назар аударыңыз.
Алиса да, Боб та өз ұпайларын барынша арттырғысы келеді. Алиса екі ойыншы да оңтайлы стратегияны қолданған кезде оның күтілетін ұпайы қандай болатынын білгісі келеді.
Сонымен қатар Алиса $q$ өзгертулер тобын (массив пен ұпайларды өзгерту) жасады, және ол сізден бастапқы массив үшін жауапты, сондай-ақ әрбір өзгертулер тобынан кейінгі жауаптарды табуыңызды қалайды.
Кіріс деректері
Бірінші жолда бастапқы $a$ массивінің ұзындығын білдіретін бүтін сан $n$ ($1 \le n \le 10^6$) берілген.
Екінші жолда бастапқы $a$ массивін білдіретін $n$ бүтін сан $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) берілген.
Үшінші жолда массивтегі әрбір санның ұпайын білдіретін $n$ бүтін сан $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^6$) берілген.
Келесі жолда өзгертулер топтарының санын білдіретін бүтін сан $q$ ($0 \le q \le 10$) берілген.
Төменде $q$ өзгертулер тобы сипатталған:
Әрбір өзгертулер тобы үшін бірінші жолда осы топтағы өзгертулер санын көрсететін $k_i$ ($1 \le k_i \le 10^5$) саны берілген.
Келесі $k_i$ жолдың әрқайсысында $a_{p_j}$ мәні $x_j$-ге, ал $c_{p_j}$ мәні $y_j$-ге өзгертілетінін көрсететін үш бүтін сан $p_j, x_j, y_j$ ($1 \le p_j, x_j \le n, 1 \le y_j \le 10^6$) берілген.
$p_1 < p_2 < \dots < p_{k_i}$ екеніне кепілдік беріледі.
Шығыс деректері
Барлығы $q + 1$ жол шығарыңыз, әр жолда жауапты білдіретін жылжымалы нүктелі сан болуы керек.
Бірінші жол — бастапқы массив үшін жауап, одан кейін әрбір өзгертулер тобынан кейінгі жауаптарға арналған $q$ жол шығарылады.
Стандартты жауаппен салыстырғанда салыстырмалы немесе абсолютті қателік $10^{-9}$-нен аспаса, жауап дұрыс деп есептеледі.
Мысалдар
Кіріс деректері 1
2 1 2 1 1 2 1 2 1 2 1 1 1 2
Шығыс деректері 1
1.333333333333 3.000000000000 4.000000000000
Кіріс деректері 2
6 1 1 4 5 1 4 2 3 3 3 3 3 0
Шығыс деректері 2
9.013888888889
Ескертпе
Бұл есепте кіріс деректерінің көлемі үлкен, тиімді енгізу әдісін пайдалануыңызды сұраймыз.