Hải dùng ổ khóa số để khóa tủ cá nhân tại đội tuyển. Khóa gồm có bốn vòng số, mỗi vòng gồm 10 chữ số từ 0 đến 9. Các vòng số của khóa này có thể xoay tròn theo chiều kim đồng hồ hoặc ngược lại.

Hải đặt mật khẩu khóa của mình theo thứ tự từ trên xuống dưới của vị trí chốt là \({2, 0, 2, 5}\). Mỗi lần khóa, Hải xoay các số đi; khi muốn mở thì lại đưa các số về đúng dãy \({2,0,2,5}\). Mỗi lần xoay thì một chữ số sẽ chuyển thành số kề bên trái hoặc kề bên phải của nó.

Chú ý: kề bên trái của \(0\) là \(9\), kề bên phải của \(9\) là \(0\).

Yêu cầu:
Cho biết bốn chữ số \(A, B, C, D\) lần lượt là các chữ số đang xuất hiện từ trên xuống dưới của vị trí chốt. Em hãy lập trình tính giúp Hải số lần xoay ít nhất để mở khóa.

Đầu vào

• Dữ liệu từ file văn bản \(KHOASO.INP\).
• Gồm một dòng duy nhất chứa bốn chữ số \(A\ B\ C\ D\), cách nhau bởi một dấu cách \((0 \le A, B, C, D \le 9)\).

Đầu ra

• Ghi ra file văn bản \(KHOASO.OUT\).
• Một số nguyên duy nhất là số lần xoay tối thiểu.

Ví dụ

2 3 8 1

11

Một cửa hàng trên sàn thương mại điện tử có \(N\) sản phẩm khác nhau được niêm yết với giá tiền lần lượt là \(A_1, A_2, \dots, A_N\).
Việt muốn mua hai sản phẩm, mỗi sản phẩm mua tối đa một lần, sao cho tổng số tiền phải trả nằm trong khoảng từ \(L\) đến \(R\).

Yêu cầu:
Em hãy lập trình đưa ra số tiền nhỏ nhất mà Việt phải trả khi mua hai sản phẩm khác nhau sao cho tổng tiền nằm trong đoạn \([L, R]\).

Đầu vào

• Dữ liệu từ file văn bản \(MUASAM.INP\):
• Dòng đầu tiên gồm ba số nguyên dương \(N, L, R\) \((N \le 10^6; 1 \le L \le R \le 10^9)\)
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, \dots, A_N\) \((A_i \le 10^9; 1 \le i \le N)\)

Đầu ra

• Ghi ra file văn bản \(MUASAM.OUT\)
• Một số nguyên duy nhất là số tiền nhỏ nhất có thể trả.
• Dữ liệu đảm bảo luôn tồn tại ít nhất một cách mua thỏa mãn.

Ràng buộc

• 80% số test ứng với 80% số điểm có \(N \le 10^3\)
• 20% số test còn lại không có ràng buộc gì thêm

Ví dụ

5 5 9
8 1 2 2 5

6

Thắng tham gia thử thách “check-in” trong hội chợ tết của thành phố.
Hội chợ gồm \(N\) điểm bán hàng được đánh số từ \(1\) đến \(N\).
Các điểm bán hàng được nối với nhau bởi \(M\) đường hai chiều, mỗi đường có một cửa chắn với mã khóa là một số nguyên dương. Các mã khóa trên cửa chắn là đôi một khác nhau.

Có \(K\) điểm bán hàng đặc biệt \(S_1, S_2, \dots, S_K\) là điểm “check-in” để hoàn thành thử thách.

Ở mỗi lượt chơi:

• Ban đầu tất cả các cửa chắn đều khóa
• Người chơi nhận được hai số \((X, D)\):
  • \(X\) là điểm bán hàng xuất phát
  • Chìa khóa số \(D\) mở được những cửa có mã khóa là bội của \(D\)
    • Ví dụ: chìa số 2 mở các cửa 2,4,6,8,…; chìa số 7 mở các cửa 7,14,21,…

Yêu cầu đường đi:

• Xuất phát từ điểm \(X\)
• Điểm đến là một trong các điểm đặc biệt \(S_1,\dots,S_K\)
• Số lượng con đường đi qua là nhỏ nhất

Em hãy lập trình đưa ra số lượng con đường nhỏ nhất Thắng cần đi qua cho mỗi lượt chơi.

Đầu vào

• Dữ liệu từ file văn bản HOICHO.INP:
  • Dòng đầu tiên: \(N, M, K, Q\) \((N, M, Q \le 3 \cdot 10^5; 1 \le K \le N)\)
  • Dòng thứ hai: \(K\) số nguyên dương \(S_1, \dots, S_K\) \((1 \le S_i \le N)\), các điểm bán hàng đặc biệt
  • \(M\) dòng tiếp theo, mỗi dòng ba số \(u, v, c\) \((1 \le u,v \le N; 1 \le c \le 10^6)\), biểu diễn đường hai chiều nối \(u\) và \(v\) với cửa có mã khóa \(c\)
  • \(Q\) dòng sau, mỗi dòng hai số \(X, D\) thông tin lượt chơi

Đầu ra

• Ghi ra file HOICHO.OUT
• Gồm \(Q\) dòng, dòng thứ \(i\):
  • Số con đường nhỏ nhất Thắng cần đi qua để đến một điểm check-in
  • Nếu không có cách đi, ghi -1

Ràng buộc

• 30% số test: \(Q=1\), \(D=1\)
• 15% số test khác: \(K=1\), \(D \le 10\)
• 25% số test khác: \(D \le 10\)
• 20% số test khác: \(D \le 10^4\)
• 10% số test còn lại: không có ràng buộc gì thêm

Ví dụ

5 7 2 4
4 5
3 4 14
1 2 16
2 4 5
1 4 7
4 5 9
1 3 8
3 5 4
1 2
1 5
1 1
2 4

2
-1
1
3

Nguồn: Học sinh Giỏi THPT Hà Nội năm 2020 - 2021

Trong một trò chơi di chuyển trên bảng số có quy tắc như sau:

• Bảng số gồm có \(N\) dòng và \(M\) cột; các dòng được đánh số từ \(1\) đến \(N\), từ trên xuống dưới; các cột được đánh số từ \(1\) đến \(M\), từ trái sang phải. Ô ở dòng thứ \(u\) giao với cột thứ \(v\) được gọi là ô \((u, v)\). Ô \((u, v)\) chứa một số nguyên \(A_{uv}\) không âm.

• Từ ô \((u, v)\), người chơi có thể di chuyển sang một ô có chung cạnh: \((u - 1, v)\), \((u + 1, v)\), \((u, v - 1)\), \((u, v + 1)\) hoặc di chuyển sang một ô khác có cùng giá trị và không thể di chuyển vào ô có giá trị bằng 0. Mỗi lần di chuyển tốn một đơn vị thời gian.

Yêu cầu: Cho vị trí ô xuất phát và ô đích, tìm thời gian nhỏ nhất đi từ ô xuất phát về ô đích theo luật của trò chơi.

Input

Dữ liệu vào từ tệp văn bản BAI4.INP:

• Dòng đầu tiên gồm hai số nguyên dương \(N\) và \(M\) là số dòng và số cột của bảng.
• Dòng thứ hai gồm bốn số \(x, y, z, t\) mô tả xuất phát ở ô \((x, y)\) và đích ở ô \((z, t)\).
• \(N\) dòng sau, mỗi dòng gồm \(M\) số nguyên không âm mô tả bảng số.
• Lưu ý: Mỗi số nguyên cách nhau một dấu cách. Dữ liệu đảm bảo luôn có đường đi từ ô xuất phát đến đích.

Output

Kết quả ra tệp văn bản BAI4.OUT:

• Gồm một số nguyên dương là số đơn vị thời gian nhỏ nhất để đi từ ô xuất phát đến ô đích thỏa mãn yêu cầu.

Example

5 4
1 1 5 4
1 2 3 4
5 0 0 6
7 0 8 9
0 0 10 0
11 12 13 14

9

Note

• Có thể đi như các đỉnh được tô đậm: 1, 2, 3, 4, 6, 9, 8, 10, 13, 14.
  

5 4
1 1 5 4
1 2 3 4
5 0 0 6
7 0 8 6
0 0 6 0
3 4 7 9

4

Note

• Có thể đi như các đỉnh được tô đậm: \(1, 5, 7, 7, 9.\)
  

Constraint

• Có \(40\%\) số test: \(N, M \leq 100\), \(A_{uv} < 10^9\) và các số nguyên dương trong bảng phân biệt;
• Có \(20\%\) số test khác: \(N, M \leq 1000\), \(A_{uv} < 10^9\) và các số nguyên dương trong bảng phân biệt;
• Có \(20\%\) số test khác: \(N, M \leq 1000\), \(A_{uv} < 10^9\) và các số nguyên dương trong bảng lặp lại không quá hai lần;
• Có \(20\%\) số test còn lại: \(N, M \leq 1000\), \(A_{uv} < 10^9\) và các số trong bảng có thể lặp lại nhiều lần.

Nguồn: Học sinh Giỏi THPT Hà Nội năm 2019 - 2020

Trung tâm khảo sát hang động XYZ có một robot tự hành. Robot này có thể tự di chuyển, vẽ sơ đồ, chụp các hình ảnh trong lòng hang động và truyền các thông tin về trung tâm. Thông tin về đường đi trong hang động được gửi về trung tâm chuỗi các chữ cái \(D, T, N, B\) tương ứng với việc đi theo các hướng Đông, Tây, Nam, Bắc trên la bàn được gắn trên robot (trong một đơn vị khoảng cách, hướng đi không thay đổi quy chiếu trên mặt phẳng nằm ngang với mặt đất, các hướng đi quy định ở hình bên).

Trong một lần robot thực hiện nhiệm vụ khảo sát một hang động mới, sau một thời gian di chuyển (trong quá trình di chuyển một điểm trong hang có thể được robot đi qua, đi lại nhiều lần) và truyền thông tin về trung tâm, robot gặp sự cố và không thể di chuyển về điểm xuất phát là cửa hang. Trung tâm muốn đưa robot về cửa hang bằng cách sử dụng những đoạn đường an toàn mà robot đã đi qua một cách nhanh nhất.

Yêu cầu: Cho chuỗi ký tự là thông tin đường đi của robot đã gửi về trung tâm. Hãy tìm độ dài đường đi ngắn nhất từ cửa hang đến được vị trí của robot bằng sử dụng thông tin đường đi trên.

Input

Dữ liệu vào từ tệp văn bản BAI4.INP:

• Một dòng gồm chuỗi các ký tự \(D, T, N, B\) ghi liên tiếp nhau. Số ký tự không quá \(10000\).

Output

Kết quả ra tệp văn bản BAI4.OUT:

• Độ dài đường đi ngắn nhất tìm được.

Example

DDTNDBBT

4

Note

• Hình ảnh đường đi và đường đi ngắn nhất đến vị trí của robot:
  

Constraint

• Có \(50\%\) số test độ dài xâu nhỏ hơn hoặc bằng \(1000.\)