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 i-th city is given by Fi.

Before starting of each trip, Chef's initial enjoyment is 1 unit. Whenever he visits a city with friendliness Fi, his enjoyment gets multiplied by Fi 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 p-th city changes to f, i.e. Fp = 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 109 + 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 - F1, F2, ..., FN, 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 109 + 7.

-----Constraints-----
-  1 ≤ N, Q ≤ 105 
-  1 ≤ Fi ≤ 10^9 
-  1 ≤ f ≤ 10^9 
-  1 ≤ p ≤ N 
-  1 ≤ R ≤ N 

-----Subtasks-----
Subtask #1 (5 points) : 

-  1 ≤ N ≤ 10 
-  1 ≤ Q  ≤ 1000 
-  1 ≤ Fi ≤ 10 
-  1 ≤ f ≤ 10 

Subtask #2 (15 points) : 

-  1 ≤ N ≤ 1000 
-  1 ≤ Q  ≤ 100 
-  1 ≤ Fi ≤ 109 
-  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 109 + 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.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "from math import *\ndef karatsuba(x,y):\n tmp = 10\n if x < 10 or y < 10:  return x*y \n m = max(int(log10(x)+1), int(log10(y)+1))\n if m % 2 != 0:\n  m -= 1\n m_2 = int(m/2)\n a, b = divmod(x, tmp**m_2)\n c, d = divmod(y, tmp**m_2)\n ac = karatsuba(a,c)\n bd = karatsuba(b,d)\n ad_bc = karatsuba((a+b),(c+d)) - ac - bd\n return ((ac*(10**m)) + bd + ((ad_bc)*(10**m_2)))\n \ndef solve(array, r):\n i = 0\n res = 1\n while i * r < len(array):\n  res = karatsuba(res, array[i * r])\n  i += 1\n return ' '.join((str(res)[0], str(res % (10**9 + 7))))\n\ndef frjump():\n N = int(input())\n friendliness = list(map(int, input().split()))\n Q = int(input())\n for _ in range(Q):\n  query = list(map(int, input().split()))\n  if query[0] == 1:\n   friendliness[query[1]-1] = query[2]\n  else:\n   types, R = query\n   print(solve(friendliness, R))\n\ndef __starting_point():\n frjump()\n__starting_point()"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 20901