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!