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

Xét một căn nhà có chiều ngang và chiều dài vô cực. Ta biểu diễn căn nhà trên hệ trục Descartes (Đề-các). Trong căn nhà có ~n~ bức tường có được biểu diễn bằng đường thẳng có dạng ~ax + by + c = 0~. Không tồn tại ba bức tường đồng quy tại một điểm. Các bức tường sẽ chia căn nhà thành một số phòng (kể cả các phòng không được bao hoàn toàn bởi các bức tường). Mỗi bức tường sẽ được lắp gương ở đúng một trong hai mặt của bức tường.

Xét hai đường thẳng giao nhau sẽ tạo ra bốn góc, trong đó có hai góc sẽ có một mặt tường và một mặt gương, ta lắp cửa thông nhau tại hai góc này (tức hai phòng chứa hai góc này sẽ có cửa thông nhau).

Sau đó bạn sẽ sơn các căn phòng, và thỏa các điều kiện sau:

• Mỗi phòng được sơn đúng một màu.
• Hai phòng có cửa thông nhau phải có cùng màu.
• Số màu là nhiều nhất có thể.

Bạn cần tìm cách lắp gương sao cho số màu có thể tô cho các phòng là nhiều nhất có thể.

Input

Bạn cần tải về ~10~ file input input_01.txt, input_02.txt, ..., input_10.txt tại đây. Dữ liệu ở mỗi file có dạng:

• Dòng đầu nhập vào ~n~ là số bức tường trong căn nhà.
• ~n~ dòng tiếp theo, mỗi dòng nhập ba số ~a, b, c~ (~|a|, |b|, |c| \le 10^9, a^2 + b^2 > 0, c \neq 0~).

Output

Với mỗi file input_xx.txt, bạn sẽ nộp file output tương ứng output_xx.txt:

• Dòng đầu in ra ~c~ là số màu tô được trong phương án lắp gương của bạn.
• Dòng thứ hai in ra ~n~ số nguyên dương, trong đó, số thứ ~i~ sẽ in ra ~0~ nếu bạn lắp gương ở mặt tường hướng về tâm ~(0, 0)~, ~1~ nếu ngược lại.

Bạn cần nộp toàn bộ file output trong một file zip.

Sample Input

5
-9 39 43
-1 35 -7
-38 49 -47
27 15 10
30 24 5

Sample Output

9
0 0 0 1 0

Subtask

Scoring

Gọi ~J~ là số màu của ban tổ chức tìm được, ~P~ là số màu bạn tìm được, ~T~ là số điểm của test, điểm của bạn trong test được tính như sau:

Quốc gia A được biểu diễn là một cây vô hướng với ~n~ thành phố được nối bởi ~n-1~ đường đi. Chính phủ đang thiết kế hệ thống cơ sở dữ liệu để đánh dấu các vùng xanh để chuẩn bị cho các trường hợp có thiên tai, dịch bệnh xảy ra.

Ta sẽ gọi máy tính lưu toàn bộ cơ sở dữ liệu là máy chủ, các máy của người dân là máy trạm.

Khi thiên tai xảy ra, chính phủ sẽ đánh dấu các vùng xanh, bao gồm một số nguyên dương các thành phố liên thông với nhau (tức, hai thành phố trong vùng xanh luôn đi được tới nhau mà không cần đi ra khỏi vùng xanh).

Máy chủ và các máy trạm đều biết thông tin của cây, tuy nhiên chỉ có máy chủ mới biết thông tin của các vùng xanh và sẽ có một số thời điểm các vùng xanh được cập nhật.

Một quá trình tương tác giữa máy trạm và máy chủ diễn ra như sau:

1. Khi người dân cần biết thông tin về một số vùng xanh, họ sẽ liệt kê ra một danh sách gồm thành phố họ đang sống và một số thành phố có đường đi trực tiếp với thành phố đó, ta gọi danh sách này là ~P~ (với ~P_0~ là thành phố của họ). Họ cần biết trong ~P~ có tồn tại thành phố thuộc vùng xanh hay không

2. Họ sẽ gửi một xâu nhị phân rồi gửi cho máy chủ, ta gọi là xâu ~S~.

3. Máy chủ nhận xâu nhị phân ~S~, gửi về máy trạm xâu nhị phân ~T~.

4. Máy trạm nhận xâu nhị phân ~T~ và cho biết một thành phố trong danh sách ~P~ thuộc vùng xanh hoặc thông báo không có thành phố nào trong danh sách ~P~ thuộc vùng xanh.

Hãy thiết kế máy chủ và máy trạm sao cho tổng lượng thông tin cần gửi là ít nhất (xem chi tiết ở phần subtask và scoring).

Implementation

Client

Bạn cần cài đặt:

namespace client

Trong client, bạn cần cài đặt các hàm sau:

void init(vector <int> par)

• Mảng ~par~ có độ dài cho ~n - 1~, biểu diễn các cạnh trong đồ thị, trong đó, với mỗi ~i~ thì có cạnh nối giữa ~i + 1~ và ~par_i~ trên cây (~0 \le i < n - 1~, ~par_i\le i~).

string request(vector <int> P)

• Mảng ~P~ sẽ là danh sách mà người dân muốn kiểm tra, trong đó, ~P_0~ sẽ là thành phố người đó đang sống và có đường đi trực tiếp đến ~P_i~ (~i > 0~). Hàm trả về xâu nhị phân ~S~, xâu này sẽ được gửi cho máy chủ.

int answer(string T)

• Xâu ~T~ là xâu được gửi về từ máy chủ sau khi thực hiện lệnh request. Bạn cần trả về một thành phố trong danh sách ~P~ thuộc vùng xanh hoặc trả về ~-1~ nếu không tồn tại.

Server

Bạn cần cài đặt:

namespace server

Trong server, bạn cần cài đặt các hàm sau:

void init(vector<int> par)

• Mảng ~par~ có độ dài cho ~n - 1~, biểu diễn các cạnh trong đồ thị, trong đó, với mỗi ~i~ thì có cạnh nối giữa ~i + 1~ và ~par_i~ trên cây (~0 \le i < n - 1~, ~par_i\le i~).

void update(vector<int> green)

• Mảng green chứa thông tin các thành phố thuộc vùng xanh.
• Lưu ý: Sau truy vấn này, chỉ có các thành phố này thuộc vùng xanh, các thành phố không trong danh sách này sẽ nằm ngoài vùng xanh.

string query(string S)

• Xâu nhị phân ~S~ được gửi từ máy trạm, hàm cần trả về một xâu nhị phân ~T~.

Note

• Được phép khai báo thêm biến và hàm toàn cục trong hai namespace hoặc ngoài hai namespace, nhưng không được đặt tên hàm là main.
• Các hàm trong cùng một namespace sẽ dùng chung dữ liệu, các biến toàn cục nằm ngoài hai namespace sẽ bị reset khi truyền thông tin giữa hai hàm.

Subtask

Trong mọi subtask: ~5 \le n \le 65536~.

Trong mỗi test, hàm 'update' và 'request' sẽ được gọi tối đa ~1000~ lần.

Scoring

• Gọi ~d = |S| + |T|~ trong mỗi lần request và query.
• ~D = max(d)~ trong mọi lần request và query.
• ~D_{max} = max(D)~ trong mọi test của một subtask và ~T~ là điểm của subtask đó, điểm của bạn cho subtask đó được tính như sau: