Giỗ Tổ Hùng Vương

Truyền thuyết kể rằng vào thời các vua Hùng Vương, khi những dấu tích đầu tiên của giang sơn đang dần hình thành, các ngài gửi gắm một kho báu thiêng nhằm gìn giữ linh khí đất Việt. Kho báu ấy không được ghi trên bất kỳ tấm bản đồ nào, mà được phong ấn dưới dạng một tọa độ bí ẩn, chỉ hiện ra vào dịp Giỗ Tổ Hùng Vương - như một dòng chảy cội nguồn vẫn âm thầm tiếp nối qua nhiều thế hệ.

Theo ghi chép cổ, mỗi năm vị trí kho báu sẽ thay đổi theo một quy luật bí ẩn, và chỉ những ai giải được mật mã tương ứng của năm đó mới có thể xác định đúng tọa độ.

Hành trình bắt đầu từ Khu di tích lịch sử Đền Hùng (núi Nghĩa Lĩnh, xã Hy Cương, thành phố Việt Trì, tỉnh Phú Thọ) với tọa độ \((x, y) = (21.268443, 105.204557)\).

Theo dòng chảy lịch sử, từ những ghi chép được ông cha truyền lại, người đời sau dần giải mã được quy luật ẩn giấu của kho báu như sau:

Từ hai số nguyên dương \(n\) và \(Y\), trong đó \(n\) là mật mã và \(Y\) là năm hiện tại.

Gọi:

• \(S\) là tổng các chữ số của \(n\)
• \(R\) là số đảo ngược của \(n\)
• \(A\) là tổng các chữ số của \(Y\)

Tọa độ kho báu \((x_0, y_0)\) được xác định bởi:

• \(x_0 = S + (A \bmod 10)\)
• \(y_0 = (R + A) \bmod 100\)

Tính khoảng cách từ điểm xuất phát đến kho báu, gọi \(K\) là phần nguyên của khoảng cách này. Hãy kiểm tra xem \(K\) có phải là số nguyên tố hay không.

Input

• Dòng 1: số nguyên dương \(n\) .
• Dòng 2: số nguyên dương \(Y\) .

Output

• In ra YES nếu \(K\) là số nguyên tố, ngược lại in ra NO.

Example

805
2024

YES

123456789012345678
2026

NO

Constraints

• Subtask 1 (50% số điểm): \(n\) có tối đa \(100\) chữ số và \(10^3 \le Y < 2 \times 10^3\).
• Subtask 2 (50% số điểm): \(n\) có từ \(100,000\) đến \(1,000,000\) chữ số và \(10^6 \le Y < 10^9\).

Truyền thuyết kể rằng vào thời các vua Hùng Vương, khi những dấu tích đầu tiên của giang sơn đang dần hình thành, các ngài gửi gắm một kho báu thiêng nhằm gìn giữ linh khí đất Việt. Kho báu ấy không được ghi trên bất kỳ tấm bản đồ nào, mà được phong ấn dưới dạng một tọa độ bí ẩn, chỉ hiện ra vào dịp Giỗ Tổ Hùng Vương - như một dòng chảy cội nguồn vẫn âm thầm tiếp nối qua nhiều thế hệ.

Theo ghi chép cổ, mỗi năm vị trí kho báu sẽ thay đổi theo một quy luật bí ẩn, và chỉ những ai giải được mật mã tương ứng của năm đó mới có thể xác định đúng tọa độ.

Hành trình bắt đầu từ Khu di tích lịch sử Đền Hùng (núi Nghĩa Lĩnh, xã Hy Cương, thành phố Việt Trì, tỉnh Phú Thọ) với tọa độ \((x, y) = (21.268443, 105.204557)\).

Theo dòng chảy lịch sử, từ những ghi chép được ông cha truyền lại, người đời sau dần giải mã được quy luật ẩn giấu của kho báu như sau:

Từ hai số nguyên dương \(n\) và \(Y\), trong đó \(n\) là mật mã và \(Y\) là năm hiện tại.

Gọi:

• \(S\) là tổng các chữ số của \(n\)
• \(R\) là số đảo ngược của \(n\)
• \(A\) là tổng các chữ số của \(Y\)

Tọa độ kho báu \((x_0, y_0)\) được xác định bởi:

• \(x_0 = S + (A \bmod 10)\)
• \(y_0 = (R + A) \bmod 100\)

Tính khoảng cách từ điểm xuất phát đến kho báu, gọi \(K\) là phần nguyên của khoảng cách này. Do thời gian lưu trữ quá lâu, mật mã \(n\) có thể đã bị xáo trộn, dẫn đến \(K\) không còn là một số nguyên tố.

Bạn được phép hoán vị lại các chữ số của \(n\) để tạo thành một mật mã mới. Hãy tìm một hoán vị của \(n\) sao cho \(K\) là số nguyên tố. Nếu có nhiều cách, hãy in ra mật mã lớn nhất. Nếu không tồn tại, in \(-1\).

Input

• Dòng 1: Số nguyên dương \(n\).
• Dòng 2: Số nguyên dương \(Y\).

Output

• Mật mã lớn nhất thỏa mãn yêu cầu đề bài, hoặc \(-1\) nếu không tồn tại.

Example

969613
2005

996631

68062
2027

-1

Constraints

• Subtask 1 (20% số điểm): \(n \le 10^{9}\) , \(10^3 \le Y < 2 \times 10^3\).
• Subtask 2 (30% số điểm): \(n\) có tối đa \(1000\) chữ số , \(10^3 \le Y < 2 \times 10^3\).
• Subtask 3 (50% số điểm): \(n\) có từ \(100.000\) đến \(1.000.000\) chữ số , \(10^6 \le Y < 2 \times 10^9\).

Hằng năm, vào ngày mùng 10 tháng 3 âm lịch — ngày lễ Giỗ Tổ Hùng Vương, người dân cả nước lại cùng nhau trở về Khu di tích lịch sử Đền Hùng, tọa lạc trên quần thể núi Nghĩa Lĩnh linh thiêng, thuộc tỉnh Phú Thọ để dâng hương tưởng nhớ các vua Hùng Vương và bày tỏ lòng biết ơn tổ tiên.

Dù ai đi ngược về xuôi, nhớ ngày Giỗ Tổ mùng mười tháng ba.

Không chỉ là dịp tưởng nhớ cội nguồn dân tộc, đây còn là một lễ hội lớn mang đậm bản sắc văn hóa Việt Nam, nơi diễn ra nhiều hoạt động văn hóa truyền thống và trò chơi dân gian. Trong không khí trang nghiêm mà vẫn rộn ràng ấy, hàng vạn người từ khắp mọi miền đất nước cùng hội tụ, tạo nên sự gắn kết bền chặt trong tinh thần đoàn kết và sẻ chia.

Trong lễ hội năm nay có một trò chơi rất thú vị, thu hút đông đảo người tham gia.

Quản trò viết lên bảng một dãy số chỉ gồm các chữ số lẻ mà ông yêu thích: \(1, 3, 5, 7, 9\).
Sau đó, ông tiết lộ một phần của dãy số bí ẩn: \(5, 7, 1, 7, 7, 3, 9, 1, 9, 9, 7, 5,\dots\)

Ông nói:

“Dãy số này tuân theo một quy luật rất đơn giản.
Ai tìm được số thứ n, người đó sẽ chiến thắng.”

Yêu cầu

Cho số nguyên dương n, hãy tìm giá trị của số hạng thứ n của dãy.

Input

• Một số nguyên dương \(n\) duy nhất (\(1 \le n \le 10^{18}\)).

Output

• In ra một chữ số là số hạng thứ \(n\) của dãy tìm được.

Example

1

5

50

9

100

3

Constraints

• Nhóm 1 (50% số điểm) : \(n \le 10^{6}\).
• Nhóm 2 (50% số điểm) : \(n \le 10^{18}\).

Hằng năm, vào ngày mùng 10 tháng 3 âm lịch — ngày lễ Giỗ Tổ Hùng Vương, người dân cả nước lại cùng nhau trở về Khu di tích lịch sử Đền Hùng, tọa lạc trên quần thể núi Nghĩa Lĩnh linh thiêng, thuộc tỉnh Phú Thọ, để dâng hương tưởng nhớ các vua Hùng và bày tỏ lòng biết ơn tổ tiên.

Lễ hội năm nay không chỉ có các trò chơi cá nhân như Kho báu Đền Hùng, Khôi phục mật mã, Quản trò trò chơi..., mà còn mở rộng thêm nhiều hoạt động đồng đội nhằm tôn vinh tinh thần đoàn kết, cùng nhau hướng về cội nguồn dân tộc.

Trong đó, hoạt động nổi bật mang tên “Dòng người tiến lễ” được tổ chức dành cho các đoàn du khách. Mỗi đoàn khi tham gia được xếp thành một hàng gồm \(n\) người, đánh số từ \(1\) đến \(n\) theo thứ tự đứng. Người thứ \(i\) mang một chỉ số \(a_i\) thể hiện mức độ gắn kết và hòa hợp trong không khí lễ hội.

Trong quá trình diễn ra hoạt động, ban tổ chức đưa ra \(q\) tình huống kiểm tra. Mỗi tình huống tương ứng với một đoạn liên tiếp \([l, r]\) trong hàng người của một đoàn. Để tăng sự gắn kết, người quản trò được phép thực hiện tối đa \(k\) lần “lan tỏa năng lượng”, mỗi lần chọn đúng một người bất kỳ trong đoạn và tăng chỉ số của người đó thêm \(1\) đơn vị. Không được giảm chỉ số, và mỗi lần lan tỏa chỉ tác động lên đúng một người.

Một đoạn được coi là “đoàn kết” nếu sau khi thực hiện tối ưu không quá \(k\) lần lan tỏa, tất cả những người trong đoạn có thể trở nên có cùng chỉ số.

Nhiệm vụ của bạn là với mỗi truy vấn độc lập \([l, r]\) , hãy xác định xem đoạn đó có thể trở thành “đoàn kết” hay không. Nếu có thể, in YES, ngược lại in NO.

Input

• Dòng 1: ba số nguyên \(n, k, q\) (\(1 \le n, q \le 2 \cdot 10^5, 0 \le k \le 10^{8}\)).
• Dòng 2: \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^8\)).
• \(q\) dòng tiếp theo: mỗi dòng gồm hai số nguyên \(l, r\) (\(1 \le l \le r \le n\)).

Output

• Với mỗi truy vấn, in YES nếu đoạn \([l, r]\) có thể trở thành “đoàn kết”, ngược lại in NO.

Example

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

YES
NO
NO

Constraints

• Subtask 1 (50% số điểm): \(n,k,q,a \le 10^3\).
• Subtask 2 (50% số điểm): \(n,q \le 2 \times 10^5\) , \(k,a\le 10^8\).

Mỗi dịp Giỗ Tổ Hùng Vương, dòng người từ khắp mọi miền đất nước lại cùng hướng về vùng đất linh thiêng để tưởng nhớ cội nguồn. Trải qua hàng nghìn năm lịch sử, hệ thống đường đi kết nối các vùng đã hình thành nên một mạng lưới rộng lớn, bao gồm cả những con đường cổ xưa lẫn các tuyến kết nối hiện đại.
Tuy nhiên, theo những ghi chép được lưu truyền qua nhiều thế hệ, hành trình tối ưu không chỉ phụ thuộc và khoảng cách địa lý mà còn chịu ảnh hưởng bởi một quy luật đặc biệt, được xác định bởi "mật mã năm" - một cơ chế cổ xưa dùng để định hướng con đường hiệu quả nhất.
Hệ thống giao thông được mô hình hoá thành một đồ thị vô hướng có trọng số gồm \(N\) đỉnh và \(M\) cạnh. Mỗi đỉnh biểu diễn một vùng đất, và mỗi cạnh biểu diễn một con đường hai chiều giữa hai vùng. Đỉnh thứ \(i\) có toạ độ \((x_i,y_i)\) trên mặt phẳng, và mỗi cạnh nối hai đỉnh \(u, v\) có chi phí di chuyển là \(w\).
Cho hai số nguyên dương \(n\) và \(Y\), trong đó \(n\) là mật mã và \(Y\) là năm hiện tại. Từ đó xác định:

• \(S\) : tổng các chữ số của \(n\)
• \(R\) : số đảo ngược của \(n\)
• \(A\) : tổng các chữ số của \(Y\)

Xét một điểm đặc biệt trên mặt phẳng:
\(\quad \quad \quad \quad \quad \quad x_0 = S + (A \bmod 100), \quad y_0 = (R + A) \bmod 10\)
Gọi \(T\) là đỉnh trong đồ thị có khoảng cách Euclid đến điểm \((x_0,y_0)\) là nhỏ nhất. Nếu có nhiều đỉnh thoả mãn, chọn đỉnh có chỉ số nhỏ nhất.
Đỉnh \(T\) chính là điểm đến cuối cùng của hành trình.

Do đặc thù của hệ thống đường cổ, tồn tại những vùng đất có khả năng "tăng tốc hành trình" nếu được lựa chọn đúng cách.

Bạn được phép chọn một đỉnh bất kỳ trên đường đi từ đỉnh \(1\) đến đỉnh \(T\) làm checkpoint.

• Khi hành trình đi qua checkpoint, một trạng thái đặc biệt được kích hoạt.
• Từ thời điểm kích hoạt thì: \(L\) cạnh tiếp theo trên đường đi sẽ có chi phí bằng \(\left\lfloor \frac{w}{2} \right\rfloor\). Nếu số cạnh còn lại nhỏ hơn \(L\), thì tất cả các cạnh còn lại đều được giảm.
• Trạng thái đặc biệt chỉ được kích hoạt đúng một lần.

Việc lựa chọn checkpoint có ảnh hưởng toàn cục đến kết quả cuối cùng và cần được tối ưu hoá cẩn thận.

Yêu cầu

Hãy xác định chi phí nhỏ nhất để đi từ đỉnh \(1\) đến đỉnh \(T\).

Input

• Dòng 1: ba số nguyên \(N,M\) \((1 \le N,M \le 10^4)\)
• Dòng 2: số nguyên \(n\) \((n \le 10^{18})\)
• Dòng 3: số nguyên \(Y\) \((1 \le Y \le 10^9)\)
• Dòng 4: số nguyên \(L\) \((1 \le L \le 100)\)
• \(N\) dòng tiếp theo: mỗi dòng gồm hai số thực \(x_i , y_i\) \((1 \le x_i , y_i \le 10^7)\)
• \(M\) dòng tiếp theo: mỗi dòng gồm ba số nguyên \(u,v,w\)

Output

• In ra một số nguyên duy nhất là chi phí nhỏ nhất.

Example

5 6
123
2024
1
0 0
2 1
4 1
6 1
8 1
1 2 4
2 3 4
3 4 4
4 5 4
1 3 4
2 5 20

10

Constraints

• Subtask 1 (50% số điểm):

  • \(1 \le N , M \le 10^3\).
  • \(1 \le n \le 10^{6}\)
  • \(1 \le Y , w \le 10^3\).
  • \(1 \le L \le 10\)

• Subtask 2 (50% số điểm):

  • \(1 \le N , M \le 10^4\)
  • \(1 \le n \le 10^{18}\)
  • \(1 \le Y , w \le 10^9\).
  • \(1 \le L \le 100\)