Bạn được cho một hoán vị ~P~ gồm ~N~ phần tử. Dựng một đồ thị vô hướng không trọng số gồm ~N~ đỉnh sao cho: tồn tại cạnh nối từ ~i~ đến ~j~ nếu như ~(i-j)\times (P_i-P_j)<0~. Bạn được cho ~Q~ truy vấn, mỗi truy vấn gồm ba số nguyên dương ~u,l,r~. Nhiệm vụ của bạn là với mỗi truy vấn, hãy tính tổng các giá trị ~D(u,v)~ thỏa mãn ~l\le D(u,v)\le r~ với mọi ~v~ từ ~1~ đến ~n~.

Trong đó, ~D(u,v)~ là độ dài đường đi ngắn nhất từ ~u~ đến ~v~, ~D(u,v)=+\infty~ nếu như không tồn tại đường đi từ ~u~ đến ~v~.

Input

Dòng đầu tiên gồm hai số nguyên dương ~N~ và ~Q~ tương ứng với số lượng phần tử của hoán vị ~P~ và số lượng truy vấn (~1\le N,Q\le 10^5~).

Dòng thứ hai gồm ~N~ số nguyên dương ~P_1,P_2,\dots,P_N~ (~1\le P_i\le N~). Dữ liệu đảm bảo các giá trị ~P_i~ đôi một phân biệt.

Cuối cùng là ~Q~ dòng, mỗi dòng gồm ba số nguyên dương ~u,l,r~ mô tả các truy vấn (~1\le l\le r\le N,1\le u\le N~).

Output

Với mỗi truy vấn, in ra kết quả trên một dòng tương ứng với kết quả của truy vấn đó.

Scoring

Sample Input 1

6 2
4 1 5 3 6 2
1 1 1
2 1 2

Sample Output 1

3
5

Cho ~29~ điểm trên mặt phẳng tọa độ được đánh số từ ~0~ đến ~28~, điểm thứ ~i~ được mô tả bởi cặp số ~(x_i,y_i)~, với ~x_i,y_i~ lần lượt là hoành độ và tung độ (~x_i,y_i~ đều là số nguyên không âm). Nhiệm vụ của bạn là cần chọn ~8~ trong số ~29~ điểm sao cho trung bình cộng hoành độ của ~8~ điểm được chọn là một số nguyên và trung bình cộng tung độ của ~8~ điểm cũng là một số nguyên.

Hiện tại đang có một khe nhớ gồm ~64~ ô (tạm gọi là mảng ~a~), được đánh số từ ~0~ đến ~63~, mỗi khe nhớ có thể lưu trữ được ~30~ bit nhị phân. Bạn được phép thực hiện ba loại thao tác cập nhật như sau:

• ~add(i,j,k)~ (~0\le i,j,k\le 63~): Tính giá trị của ~a_i+a_j~ sau đó gán vào giá trị của ~a_k~. Nếu giá trị thu được biểu diễn nhiều hơn ~30~ bit thì chỉ lấy ~30~ bit cuối.

• ~sub(i,j,k)~ (~0\le i,j,k\le 63~): Tính giá trị của ~a_i-a_j~ sau đó gán vào giá trị của ~a_k~. Nếu giá trị thu được là số âm thì cập nhật ~a_k:=0~.

• ~half(i,j)~ (~0\le i,j\le 63~): Tính giá trị của ~\lfloor \frac{a_i}2 \rfloor~ sau đó gán vào giá trị của ~a_j~.

Lưu ý: Trong một thao tác, các giá trị ~i,j,k~ không nhất thiết phải đôi một phân biệt mà có thể bằng nhau.

Ngoài ra, bạn không được phép truy cập giá trị trực tiếp vào các khe nhớ mà chỉ được phép thực hiện truy vấn kiểm tra như sau:

• Chọn một tập gồm một số khe nhớ, khi đó bạn sẽ được trả về kết quả xem có tồn tại hai khe nhớ mang giá trị bằng nhau hay không.

Ban đầu, các giá trị ~x_i,y_i~ được lưu trước vào các khe nhớ như sau: ~a_{2i}=x_i,a_{2i+1}=y_i~ với mọi ~i~ từ ~0~ đến ~28~. Các khe nhớ còn lại ban đầu có giá trị bằng ~0~.

Chi tiết cài đặt

Thí sinh cần cài đặt hàm sau:

vector<int> solve()

• Hàm này sẽ được gọi tối đa ~100~ lần bởi trình chấm.

• Hàm này cần trả về chỉ số của ~8~ trong số ~29~ điểm được chọn, các điểm này phải thỏa mãn điều kiện đã được nêu ở đề bài. Nếu có nhiều phương án khác nhau thỏa mãn thì bạn chỉ cần đưa ra một trong số chúng.

Trong hàm solve(), thí sinh được phép gọi các hàm sau (thí sinh cần khai báo trước thư viện cpointlib.h để có thể sử dụng các hàm này):

void add(int i, int j, int k)

• ~i,j,k~: Chỉ số của các vị trí cần thiết để thực hiện thao tác cập nhật. Cần phải đảm bảo ~0\le i,j,k\le 63~. Các giá trị này không nhất thiết phải đôi một phân biệt.

• Hàm này sẽ thực hiện cập nhật ~a_k:=a_i+a_j~. Nếu sau khi cập nhật, biểu diễn số ~a_k~ có trên ~30~ bit thì chỉ giữ ~30~ bit cuối.

void sub(int i, int j, int k)

• ~i,j,k~: Chỉ số của các vị trí cần thiết để thực hiện thao tác cập nhật. Cần phải đảm bảo ~0\le i,j,k\le 63~. Các giá trị này không nhất thiết phải đôi một phân biệt.

• Hàm này sẽ thực hiện cập nhật ~a_k:=a_i-a_j~. Nếu sau khi cập nhật, ~a_k~ là số âm thì cập nhật lại ~a_k:=0~.

void half(int i, int j)

• ~i,j~: Chỉ số của các vị trí cần thiết để thực hiện thao tác cập nhật. Cần phải đảm bảo ~0\le i,j\le 63~. Các giá trị này không nhất thiết phải đôi một phân biệt.

• Hàm này sẽ thực hiện cập nhật ~a_j:=\lfloor \frac{a_i}2 \rfloor~.

Lưu ý: Trong một lần gọi hàm solve(), tổng số lần gọi hàm add(), sub(), half() không được vượt quá ~10^5~.

bool ask(string s)

• ~s~: Xâu nhị phân mô tả trạng thái chọn hay không chọn của các khe nhớ để kiểm tra. Cần phải đảm bảo xâu ~s~ có đúng ~64~ ký tự và chỉ được chứa các ký tự 0 hay 1.

• Với mọi ~i~ thỏa mãn ~0\le i\le 63~, nếu ~s_i=~1 thì khe nhớ thứ ~i~ sẽ được chọn để kiểm tra.

• Hàm này sẽ trả về true nếu tồn tại hai khe nhớ trong số các khe nhớ được chọn mang giá trị bằng nhau. Ngược lại, hàm sẽ trả về false.

Ngoài ra, thí sinh được phép cài đặt các biến, các hàm toàn cục, nhưng không được phép có hàm main().

Ràng buộc

• Với mọi ~i~ từ ~0~ đến ~28~, ~0\le x_i,y_i<2^{30}~.

Trình chấm của bài này không mang tính thích ứng. Điều này tương đương với việc các giá trị ~x_i,y_i~ sẽ được cố định từ đầu và không thay đổi trong suốt quá trình chương trình của bạn tương tác với trình chấm.

Scoring

Cách tính điểm

Giả sử test có tối đa ~1~ điểm. Nếu trong bất kỳ lần gọi hàm solve() nào, tập điểm được chọn không thỏa mãn điều kiện của đề bài thì bạn sẽ được ~0~ điểm cho toàn bộ test đó. Ngược lại, gọi ~Q~ là số lần gọi hàm ask() tối đa trong một lần gọi hàm solve(). Khi đó, điểm của bạn sẽ được tính theo công thức như sau:

• Nếu ~Q>276~ thì bạn được ~0~ điểm.

• Nếu ~174 \le Q\le 276~ thì bạn được ~0.2 \times 0.95^{Q-174}~ điểm.

• Nếu ~94 \le Q< 174~ thì bạn được ~0.2 + 0.2 \times 0.95^{Q-94}~ điểm.

• Nếu ~76\le Q< 94~ thì bạn được ~0.4 + 0.5 \times 0.8^{Q-76}~ điểm.

• Nếu ~66<Q<76~ thì bạn được ~0.9 + 0.1 \times 0.8^{Q-66}~ điểm.</p>

• Nếu ~Q\le 66~ thì bạn được ~1~ điểm.

Điểm của mỗi subtask là điểm thấp nhất của một test trong subtask đó nhân với số điểm tối đa của subtask.

Sample Grader

Tải trình chấm mẫu tại đây.

Trình chấm mẫu đọc dữ liệu vào theo định dạng sau:

• Dòng ~i+1~ (~0\le i<29~): ~x_i~ ~y_i~

Trình chấm mẫu sẽ in ra một trong các kết quả sau:

• Example passed! nếu như tập điểm chương trình của bạn đưa ra thỏa mãn yêu cầu đề bài.

• Wrong answer! nếu như tập điểm chương trình của bạn đưa ra không thỏa mãn yêu cầu đề bài.

• "Invalid operation" + (loại thao tác/truy vấn không hợp lệ) nếu như chương trình của bạn thực hiện một thao tác/truy vấn không hợp lệ. Ví dụ: Nếu chương trình của bạn thực hiện thao tác sub không hợp lệ, trình chấm mẫu sẽ in ra Invalid operation sub!

Alice rất yêu thích các xâu kí tự. Với ba số nguyên dương ~N, L, R~ (~1 \le L \le R \le N~), cô đã tạo ra tập ~\Omega~ gồm tất cả các xâu độ dài ~N~ là hoán vị của ~N~ kí tự Latin in thường đầu tiên, sao cho vị trí của kí tự a trên xâu thuộc đoạn ~[L; R]~ (vị trí của các ký tự trong xâu được đánh số từ ~1~ đến ~N~).

Bob muốn tạo ra một xâu ~U~ chứa tất cả các xâu trong tập ~\Omega~ và có độ dài càng nhỏ càng tốt. Ở đây, xâu ~X~ được gọi là chứa xâu ~Y~ nếu như có thể xóa bỏ một số ký tự của xâu ~X~ (có thể không xóa ký tự nào) và giữ nguyên thứ tự của các ký tự còn lại để có được xâu ~Y~.

Tuy nhiên, Alice đã không cho Bob biết chính xác giá trị của ~N,L,R~. Thay vào đó, cô sẽ trả lời một số câu hỏi của anh. Với mỗi lần hỏi của Bob:

• Bob sẽ đưa cho Alice một xâu ~s~ có độ dài không quá ~200~. Xâu này chỉ được chứa các ký tự Latin in thường.

• Alice sẽ tính toán và trả lời cho Bob biết số xâu ~t\in \Omega~ thỏa mãn xâu ~s~ khớp với xâu ~t~ chia lấy dư cho ~379~.

Sau khi hỏi Alice một số câu hỏi, Bob sẽ trả lời xâu ~U~ mà anh tìm được. Để thể hiện sự thông minh của mình trước Alice, Bob muốn giá trị ~P=Q+|U|~ càng nhỏ càng tốt, trong đó ~Q~ là số câu hỏi Bob đã thực hiện và ~|U|~ là độ dài xâu ~U~ mà Bob trả lời. Hãy lập trình giúp Bob một chương trình tương tác với Alice để thực hiện yêu cầu trên.

Chi tiết cài đặt

Thí sinh cần cài đặt hàm sau:

string solve()

• Hàm này có thể được gọi nhiều lần bởi trình chấm.

• Hàm này cần trả về xâu ~U~ thỏa mãn điều kiện đề bài. Lưu ý là bạn không được biết trước giá trị của ~N,L,R~.

Trong hàm solve(), thí sinh được phép gọi hàm sau (thí sinh cần khai báo trước thư viện smatchlib.h để có thể sử dụng hàm này):

int ask(string s)

• ~s~: Xâu mà Bob sẽ đưa cho Alice để thực hiện câu hỏi. Xâu ~s~ chỉ được chứa các ký tự Latin in thường và có độ dài không quá ~200~.

• Hàm sẽ trả về một số nguyên không âm là số lượng xâu ~t\in \Omega~ thỏa mãn ~s~ khớp với ~t~ chia lấy dư cho ~379~.

Ngoài ra, thí sinh được phép cài đặt các biến, các hàm toàn cục, nhưng không được phép có hàm main().

Cách cài đặt và trình chấm ví dụ có thể xem tại contest material, lưu ý trình chấm ví dụ chỉ mô phỏng cách hoạt động và sẽ không được dùng để chấm chính thức.

Ràng buộc

• ~4\le N\le 13~

• ~1\le L\le R\le N~

Trình chấm của bài này không mang tính thích ứng. Điều này tương đương với việc các giá trị ~N,L,R~ sẽ được cố định từ đầu và không thay đổi trong suốt quá trình chương trình của bạn tương tác với trình chấm.

Scoring

Cách tính điểm

Giả sử test có tối đa ~1~ điểm. Nếu trong bất kỳ lần gọi hàm solve nào, xâu ~U~ bạn đưa ra không thỏa mãn với điều kiện của đề bài thì bạn sẽ được ~0~ điểm cho toàn bộ test đó. Ngược lại, điểm của bạn sẽ được tính như sau:

• Mỗi lần gọi hàm solve sẽ có điểm của lần gọi hàm đó (gọi là ~score~). Xét lần gọi hàm tương ứng, gọi giá trị ~P=Q+|U|~ là độ tối ưu kết quả của thí sinh, giá trị ~J=Q+|U|~ là độ tối ưu kết quả của ban tổ chức (~Q~ là tổng số lần thực hiện truy vấn ask, ~U~ là xâu đáp án trả về đã thỏa mãn điều kiện). Khi đó:

  • Nếu ~Q>10~ thì ~score=0~.

  • Nếu ~N<P-J~ thì ~score=0.4\times 0.9^{P-J-N-1}~.</p>

  • Nếu ~4\le P-J\le N~ thì ~score=0.4+0.4\times 0.8^{P-J-4}~.

  • Nếu ~0<P-J<4~ thì ~score=0.8+0.2\times 0.8^{P-J}~.</p>

  • Nếu ~P\le J~ thì ~score=1~.

• Điểm của một test sẽ bằng điểm (giá trị ~score~) nhỏ nhất trong tất cả lần gọi hàm solve.

Điểm của mỗi subtask là điểm thấp nhất của một test trong subtask đó nhân với số điểm tối đa của subtask.

Sample Grader

Tải trình chấm mẫu tại đây.

Trình chấm mẫu đọc dữ liệu vào theo định dạng sau:

• Dòng ~1~: ~N~ ~L~ ~R~

Trình chấm mẫu sẽ in ra một trong các kết quả sau:

• Example passed! nếu như xâu ~U~ do chương trình của bạn đưa ra thỏa mãn yêu cầu đề bài.

• Wrong answer! nếu như xâu ~U~ do chương trình của bạn đưa ra không thỏa mãn yêu cầu đề bài.

• Invalid operation! nếu như chương trình của bạn gọi hàm ask() không hợp lệ.