Divyank loves solving problems related to queries.So while solving one such problem he encountered the following problem related to DP numbers.After trying a lot he couldn't solve the problem in a very efficient manner,So he came to you with the problem.Can you help him out?

DP numbers are those numbers whose multiplication of digits is a perfect square.

Example :- 22 is a DP Number because multiplication of its digits is 2*2=4, which is a perfect square.However 23 is not a DP number.

You are given an Array of N numbers. You are required to answer Q queries of following type:-

• Type 1 :- Total number of DP numbers in a given range [L,R].
• Type 2 :- Update the number at ith index with X.
• Type 3 :- Print "Yes" if number formed by appending all the numbers in the range [L,R] to form a single number is a DP number,otherwise print "No".
• Type 4 :- Find the index of kth DP number,if there is no such number print -1.

Input:

First line consists of a two integers N Q,number of elements and total number of queries to answer.

Second line contains N space separated integers

Next Q lines will be queries .

• Query type 1 has the form "1 L R".
• Query type 2 has the form "2 i X".
• Query type 3 has the form "3 L R".
• Query type 4 has the form "4 k".

Output:

For each Query of type 1, 3 and 4 output the result in a single line.

Constraints

1 ≤ N,Q ≤ 500000

0 ≤ L,R,i ≤ N-1

0 ≤ A[i],X,k ≤ 1000000000