Chef and cities

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef likes to travel a lot. Every day Chef tries to visit as much cities as possible. Recently he had a quite a few trips of great Chefland for learning various recipes. Chefland had N cities numbered from 1 to N. People in Chefland are very friendly, friendliness of ith city is given by F_{i}.
Before starting of each trip, Chef's initial enjoyment is 1 unit. Whenever he visits a city with friendliness F_{i}, his enjoyment gets multiplied by F_{i} units.
City 1 is the home city of Chef. He starts each trip from his home city. Before starting a trip, he chooses a parameter R which denotes that he will start from city 1, and go to city 1 + R, then to 1 + 2 * R, then to 1 + 3 * R, till 1 + i * R such that i is largest integer satisfying 1 + i * R ≤ N.
Now, Chef wants you to help him recreate his visit of the cities. Specifically, he will ask you Q queries, each of which can be of following two types.
 1 p f : friendliness of pth city changes to f, i.e. F_{p} = f
 2 R : Find out the total enjoyment Chef will have during this trip. As Chef does not like big numbers, he just asks you to output two things, first digit of the enjoyment and value of enjoyment modulo 10^{9} + 7.
Input
There is a single test case.
First line of input contains a single integer N, denoting number of cities in Chefland.
Second line of the input contains N space separated integer  F_{1}, F_{2}, ..., F_{N}, denoting the friendliness of the cities in order from 1 to N.
Next line contains an integer Q, denoting number of queries.
For each of the next Q queries, each line corresponds to one of the two types of the query. First there will be an integer denoting the type of the query, followed by the actual query. For query of type 1, there will be three space separated integers "1 p f" as defined above. For query of type 2, there will be two space separated integers "2 R ", as defined above.
Output
For each query of type 2, output two space separated integers, first digit of Chef's enjoyment in this trip followed by the value of enjoyment modulo 10^{9} + 7.
Constraints
 1 ≤ N, Q ≤ 10^{5}
 1 ≤ F_{i} ≤ 10^9
 1 ≤ f ≤ 10^9
 1 ≤ p ≤ N
 1 ≤ R ≤ N
Subtasks
Subtask #1 (5 points) :
 1 ≤ N ≤ 10
 1 ≤ Q ≤ 1000
 1 ≤ F_{i} ≤ 10
 1 ≤ f ≤ 10
Subtask #2 (15 points) :
 1 ≤ N ≤ 1000
 1 ≤ Q ≤ 100
 1 ≤ F_{i} ≤ 10^{9}
 1 ≤ f ≤ 1000
Subtask #3 (80 points) :
 original constraints
Example
Input: 5 1 2 3 4 5 3 2 1 1 3 10 2 2 Output: 1 120 5 50
Explanation
In the first query, Chef is going to visit cities 1, 2, 3, 4, 5 in order. At the end of the trip, his total enjoyment will be 1 * 2 * 3 * 4 * 5 = 120. First digit of enjoyment is 1 and 120 modulo 10^{9} + 7 is 120.
In the third query, Chef is going to visit cities 1, 3, 5 in order. At the end of the trip, his total enjoyment will be 1 * 10 * 5 = 50.
Author:  fiter 
Tester:  iscsi 
Editorial  http://discuss.codechef.com/problems/FRJUMP 
Tags  fiter, june16, log, medium, sqrtdecomp 
Date Added:  16022016 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions