Some country consists of ( n + 1) cities, located along a straight highway. Let's number the cities with consecutive integers from 1 to n + 1 in the order they occur along the highway. Thus, the cities are connected by n segments of the highway, the i -th segment connects cities number i and i + 1 . Every segment of the highway is associated with a positive integer a i > 1 — the period of traffic jams appearance on it. In order to get from city x to city y ( x < y ), some drivers use the following tactics. Initially the driver is in city x and the current time t equals zero. Until the driver arrives in city y , he perfors the following actions: if the current time t is a multiple of a x , then the segment of the highway number x is now having traffic problems and the driver stays in the current city for one unit of time (formally speaking, we assign t = t + 1 ); if the current time t is not a multiple of a x , then the segment of the highway number x is now clear and that's why the driver uses one unit of time to move to city x + 1 (formally, we assign t = t + 1 and x = x + 1 ). You are developing a new traffic control system. You want to consecutively process q queries of two types: determine the final value of time t after the ride from city x to city y ( x < y ) assuming that we apply the tactics that is described above. Note that for each query t is being reset to 0 . replace the period of traffic jams appearing on the segment number x by value y (formally, assign a x = y ). Write a code that will effectively process the queries given above. The first line contains a single integer n ( 1 ≤ n ≤ 10 5 ) — the number of highway segments that connect the n + 1 cities. The second line contains n integers a 1 , a 2 , ..., a n ( 2 ≤ a i ≤ 6 ) — the periods of traffic jams appearance on segments of the highway. The next line contains a single integer q ( 1 ≤ q ≤ 10 5 ) — the number of queries to process. The next q lines contain the descriptions of the queries