Furiosa AI đang phát triển NPU (Neural Processing Unit) giúp tăng tốc quá trình học và suy luận của các mô hình trí tuệ nhân tạo so với các bộ xử lý (processing unit) truyền thống. Một chương trình chạy trên bộ xử lý thông thường sẽ xử lý dữ liệu được lưu trữ trên máy chủ (host) bằng cách sử dụng nhiều loại toán tử khác nhau để tính toán ra giá trị mong muốn. Trong bài toán này, chúng ta đơn giản hóa quá trình đó và xem xét môi trường sau:

• Máy chủ có không gian lưu trữ $1\,000\,000$ dữ liệu, mỗi không gian được đánh số từ $0$ đến $999\,999$.
• Mỗi toán tử nhận một hoặc nhiều dữ liệu đầu vào và tính toán ra một dữ liệu đầu ra. Các toán tử cũng được đánh số từ $0$ đến $999\,999$.
• Chương trình được biểu diễn bằng BNF (Backus-Naur Form) như sau: <number> ::= 0 | 1 | ... | 999999 <value> ::= <number> | <number>(<list>) <list> ::= <value> | <list>,<value>
• Chương trình tính toán một giá trị duy nhất. Nói cách khác, chương trình là một chuỗi ký tự tương ứng với <value>.
• Giá trị của <value> được tính như sau:
  • Nếu <value> được biểu diễn dưới dạng <number>, đó là dữ liệu được lưu trữ trong không gian số <number> của máy chủ trước khi chương trình bắt đầu.
  • Nếu <value> được biểu diễn dưới dạng <number>(<list>), đó là dữ liệu đầu ra được tính toán bằng cách sử dụng toán tử số <number> với các <value> trong <list> làm dữ liệu đầu vào theo thứ tự.
• Trong một chương trình, cùng một <number> không xuất hiện nhiều lần.

NPU mà Furiosa AI phát triển có thể thực thi cùng một chương trình nhanh hơn bộ xử lý thông thường, nhưng cần một trình biên dịch để biên dịch lại chương trình thành các lệnh cấp thấp mà NPU sử dụng. Vì mức tiêu thụ bộ nhớ và thời gian thực thi của chương trình thay đổi tùy thuộc vào cách biên dịch, nên cần một trình biên dịch tối ưu để sử dụng NPU hiệu quả.

NPU có bộ nhớ lưu trữ được $M$ dữ liệu, mỗi không gian bộ nhớ được đánh số từ $0$ đến $M-1$. NPU hỗ trợ ba loại lệnh sau:

• a >> b
  • Sao chép dữ liệu từ vị trí a của máy chủ vào vị trí b của bộ nhớ. ($0 \le a < 1\,000\,000$; $0 \le b < M$). Nếu dữ liệu đã tồn tại, nó sẽ bị ghi đè.
• a << b
  • Sao chép dữ liệu từ vị trí b của bộ nhớ vào vị trí a của máy chủ. ($0 \le a < 1\,000\,000$; $0 \le b < M$). Nếu dữ liệu đã tồn tại, nó sẽ bị ghi đè.
• o = w | m1 m2 ··· ml
  • Lưu trữ kết quả đầu ra của toán tử w vào vị trí o của bộ nhớ, với các giá trị tại địa chỉ m1, m2, ···, ml trong bộ nhớ được sử dụng làm dữ liệu đầu vào theo thứ tự.
  • Vị trí lưu trữ dữ liệu đầu ra phải khác với các vị trí lưu trữ dữ liệu đầu vào. Tức là $o \neq m_i$ ($1 \le i \le l$).

Chương trình NPU là một chuỗi các lệnh nêu trên; khi thực thi chương trình, các lệnh cấu thành chương trình sẽ được thực thi theo thứ tự.

Hiệu quả của chương trình được quyết định bởi nhiều yếu tố, nhưng nếu số lượng lệnh sử dụng càng ít thì khả năng chương trình đó hiệu quả càng cao. Khi được cung cấp một chuỗi ký tự tương ứng với <value>, hãy chuyển đổi nó thành một chương trình NPU tính toán giá trị của <value> và lưu vào bộ nhớ số $0$ bằng cách sử dụng ít lệnh nhất có thể.

Dữ liệu vào

Dòng đầu tiên chứa kích thước bộ nhớ $M$ của NPU. ($1 \le M \le 1\,000\,000$) Dòng thứ hai chứa chuỗi ký tự tương ứng với <value> cần tính toán. Độ dài của chuỗi này không quá $1\,000\,000$.

Dữ liệu ra

Nếu bộ nhớ của NPU không đủ để biên dịch chương trình, hãy in ra $-1$. Nếu có thể biên dịch chương trình, dòng đầu tiên in ra số lượng lệnh tối thiểu để tính toán <value>. Từ dòng tiếp theo, in ra các lệnh cấu thành chương trình, mỗi lệnh một dòng theo đúng thứ tự. Giữa các token của một lệnh phải có một khoảng trắng. Nếu có nhiều đáp án, hãy in ra bất kỳ đáp án nào.

Ví dụ

Ví dụ 1

7
71(72(41,42),73(43,44))

7
41 >> 3
42 >> 4
43 >> 5
44 >> 6
1 = 72 | 3 4
2 = 73 | 5 6
0 = 71 | 1 2

Ví dụ 2

3
71(72(41,42),73(43,44))

9
43 >> 2
44 >> 0
1 = 73 | 2 0
59 << 1
41 >> 2
42 >> 0
1 = 72 | 2 0
59 >> 2
0 = 71 | 1 2

Ví dụ 3

2
71(72(41,42),73(43,44))

-1