There is a social website with n fanpages, numbered 1 through n . There are also n companies, and the i -th company owns the i -th fanpage. Recently, the website created a feature called following. Each fanpage must choose exactly one other fanpage to follow. The website doesn’t allow a situation where i follows j and at the same time j follows i . Also, a fanpage can't follow itself. Let’s say that fanpage i follows some other fanpage j 0 . Also, let’s say that i is followed by k other fanpages j 1 , j 2 , ..., j k . Then, when people visit fanpage i they see ads from k + 2 distinct companies: i , j 0 , j 1 , ..., j k . Exactly t i people subscribe (like) the i -th fanpage, and each of them will click exactly one add. For each of k + 1 companies j 0 , j 1 , ..., j k , exactly people will click their ad. Remaining people will click an ad from company i (the owner of the fanpage). The total income of the company is equal to the number of people who click ads from this copmany. Limak and Radewoosh ask you for help. Initially, fanpage i follows fanpage f i . Your task is to handle q queries of three types: 1 i j — fanpage i follows fanpage j from now. It's guaranteed that i didn't follow j just before the query. Note an extra constraint for the number of queries of this type (below, in the Input section). 2 i — print the total income of the i -th company. 3 — print two integers: the smallest income of one company and the biggest income of one company. The first line of the input contains two integers n and q ( 3 ≤ n ≤ 100 000 , 1 ≤ q ≤ 100 000 ) — the number of fanpages and the number of queries, respectively. The second line contains n integers t 1 , t 2 , ..., t n ( 1 ≤ t i ≤ 10 12 ) where t i denotes the number of people subscribing the i -th fanpage. The third line contains n integers f 1 , f 2 , ..., f n ( 1 ≤ f i ≤ n ). Initially, fanpage i follows fanpage f i . Then, q lines follow. The i -th of them describes the i -th query. The first number in the l