Nam được giao nhiệm vụ sinh test cho bài toán sau:

Cho một dãy ~A~ gồm ~n~ số nguyên dương. Gọi ~A_0~ là dãy ~A~ trước khi thực hiện các truy vấn.

Thực hiện ~q~ truy vấn thuộc một trong ba dạng như sau:

1. "~\text{GCD } l\ r\ v\ x~": ~A[i] = \gcd(A[i], v^x)~ với mọi ~l\le i\le r~.

2. "~\text{LCM } l\ r\ v\ x~": ~A[i] = \text{lcm}(A[i], v^x)~ với mọi ~l\le i\le r~.

3. "~\text{CHK } l\ r~": Cho biết với mọi ~i~ trong đoạn ~[l, r]~ thì ~A_0[i] = A[i]~ hay không?

Để sinh một bộ test tốt, với mỗi truy vấn loại ~3~, Nam cần biết có bao nhiêu cách điền giá trị vào ~A[l], A[l+1],\ldots,A[r]~ sao cho thỏa mãn điều kiện đã cho.

Hãy giúp Nam giải quyết bài toán mới này.

Input

Dòng đầu nhập hai số nguyên dương ~n~, ~q~ (~1\le n,q\le 10^5~) tương ứng với độ dài dãy ~A~ và số truy vấn.

Mỗi dòng ~q~ dòng tiếp theo, nhập vào một truy vấn như trên đề bài (~1 \le l \le r \le n~, ~2 \le v\le 10^7~, ~1\le x\le 10^7~).

Output

Với mỗi truy vấn loại ~3~, gọi ~ans~ là số bộ giá trị có thể điền vào ~A[l],A[l+1],\ldots,A[r]~ sao cho thỏa điều kiện của truy vấn, nếu ~ans \le 9 \times 10^{18}~ thì in ~ans~, ngược lại in ~-1~.

Scoring

Sample Input 1

5 6
CHK 2 4
LCM 1 1 10 1
GCD 1 3 9 1
GCD 1 5 9 5
CHK 1 3
CHK 1 5

Sample Output 1

-1
27
3267