CF498D Traffic Jams in the Land

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: 1. 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 $ . 2. 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.

N/A

N/A