Mắt Nhắm Mắt Mở Contest #01

Gần đây, khi album Mắt Nhắm Mắt Mở của HIEUTHUHAI ra lò và thu hút rất nhiều người nghe, thì HIEUCHUNHAT - Koruto lại nhận được \(1\) tin sét đánh. Vài tuần trước, bạn gái của anh bỗng dưng im lặng hơn thường ngày, anh hỏi gì thì cũng đánh trống lảng, rồi tới \(1\) hôm, anh nhận được \(1\) số nguyên \(n\) và một xâu kí tự \(S\) vô cùng kì lạ từ cô ấy. Nhận ra đây là thứ có vẻ vô cùng quan trọng, anh quyết định bắt tay vào xử lí xâu kí tự này, nhưng vì đang bận ôn thi nên anh ấy đâm ra khá lười và quyết định nhờ bạn giải quyết hộ anh ấy.

Biết rằng, Koruto cho bạn \(1\) gợi ý về cách mà cô ấy đã dùng mã hóa xâu: Với mỗi kí tự \(s_i\), cô ấy lấy số thứ tự của nó trong bảng mã UNICODE, cộng thêm \(1\) lượng bằng \(n\) và tạo thành kí tự mới.

Input

• Dòng đầu chứa số nguyên \(n\) (\(1 \le n \le 10^5\)).
• Dòng thứ hai chứa xâu kí tự \(S\) (\(|S| \le 100\)).

Output

• Gồm một dòng là xâu \(S\) sau khi xử lí.

Example

145
Öþ±ąùἶĊ±ąὶú±þŽÿù±üùƅÿø±ùὴā±ąžÿù±ÿùòƱýὀþ½±þŽÿù±ôùúò±ąòĊ±ÿùź

Em thấy tụi mình không hợp tính nhau lắm, mình chia tay nhé

Sau khi mã hóa tin nhắn từ bài tập trước, Koruto điếng người khi nhận ra người mà anh yêu bấy lâu nay đã quyết định buông bỏ. Mặc dù chưa biết lý do thật sự là gì nhưng anh nghe phong phanh từ những người bạn rằng là "do mầy cọc tính quá", "do nó không thích mầy đâu", "nó lừa mầy thôi", "..." Không muốn tin vào sự thật phũ phàng, anh quyết định chọn cách trốn tránh, nhưng rồi nhận ra bản thân cần phải thay đổi rồi.

Để giúp Koruto vực lại tinh thần, Tiến sĩ Đá Orochimaru đã tạo ra 1 phần mềm giúp anh rèn luyện tinh thần. Cụ thể, trong phần mềm này, Koruto sẽ được hẹn hò với \(n\) cô gái (đương nhiên là bot thôi) và mỗi cô gái sẽ có mức độ thương tổn là \(a_i\) \((1 \le i \le n)\). Để quá trình luyện tập hiệu quả, mỗi lần Koruto sẽ làm quen với 1 cô gái và bị đá, nhận lại mức thương tổn và hồi phục để sẵn sàng bị cô gái tiếp theo đá tới khi hết bot mà thôi.

Quy tắc huấn luyện:

1. Thứ tự: Koruto có thể chọn gặp các cô gái theo bất kỳ thứ tự nào, miễn là phải trải qua đủ \(n\) mối tình.
2. Điều kiện: Anh chỉ có thể gặp một cô gái nếu chỉ số chịu đựng hiện tại lớn hơn mức thương tổn \(a_i\) của cô gái đó. Sau khi bị đá, chỉ số chịu đựng của anh sẽ giảm đi một lượng đúng bằng \(a_i\).
3. Trong một ngày: Koruto có thể bị đá bởi nhiều cô gái liên tiếp nếu chỉ số chịu đựng còn đủ.
4. Hồi phục: Nếu không đủ chỉ số chịu đựng để gặp cô gái tiếp theo, anh phải nghỉ ngơi để sang ngày hôm sau.
   • Ngày 1: Koruto bắt đầu với chỉ số chịu đựng bằng \(m\).
   • Từ Ngày 2 trở đi: Mỗi ngày mới bắt đầu, anh được cộng thêm \(k\) vào chỉ số chịu đựng hiện có (năng lượng dư từ ngày hôm trước được bảo lưu và cộng dồn với \(k\)).

Yêu cầu: Hãy giúp Tiến sĩ Đá Orochimaru tính toán số ngày tối thiểu để Koruto hoàn thành khóa huấn luyện (vượt qua tất cả \(n\) mối tình với các cô gái ảo).

Input

• Gồm 2 dòng
• Dòng đầu chứa số nguyên \(n, m, k\) \((1 \le n \le 10^5, 1 \le m, k \le 10^9)\)
• Dòng thứ hai chứa \(n\) số nguyên \(a_i\) \((a_i \le 10^6)\) là mức độ thương tổn của \(n\) cô gái

Output

• Gồm một dòng là số ngày tối thiểu.

Example

3 10 5
7 8 9

4

Scoring

• Subtask 1 (\(30\%\) điểm): \(n \le 10, m, k, a_i \le 100\).
• Subtask 2 (\(40\%\) điểm): \(n \le 10^3, m, k, a_i \le 10^6\).
• Subtask 3 (\(30\%\) điểm): Không có ràng buộc gì thêm (\(n \le 10^5, m, k \le 10^9, a_i \le 10^6\)).

Sau khi trải qua khóa huấn luyện khắc nghiệt của Tiến sĩ Đá Orochimaru, Koruto dành những ngày dài trong căn phòng tối, vùi mình vào những bản nhạc trong album của HIEUTHUHAI, buitruonglinh,... để cố gắng quên đi người cũ. Tuy nhiên, như HIEUTHUHAI đã hát, "âm nhạc có thể sẽ làm em buồn hoặc có thể sẽ làm em vui, đó là dao hai lưỡi..." và mỗi bản nhạc đều mang trong mình một sức mạnh tâm linh kỳ lạ.

Cụ thể, mỗi bản nhạc thứ \(i\) có một mức độ gây thương nhớ là \(a_i\) và mang cảm xúc \(b_i\). Tiến sĩ Đá phát hiện ra rằng nỗi nhớ không biến mất mà nó tồn đọng trong tâm trí. Nếu Koruto nghe một playlist mà mức độ thương nhớ \(P\) và cảm xúc \(Q\) mà playlist đó mang lại có \(|Q - P|\) lớn hơn khả năng chịu đựng là \(S\), Koruto sẽ khóc trong đêm và mơ thấy người cũ...

Yêu cầu: Hãy giúp Tiến sĩ Đá Orochimaru thống kê xem có tổng cộng bao nhiêu playlist khiến Koruto phải mơ thấy người cũ, biết rằng các bài hát trong playlist đều lấy từ danh sách gốc và Koruto không bao giờ nghe chế độ trộn nhạc ngẫu nhiên.

Input

Gồm 3 dòng:

• Dòng đầu chứa hai số nguyên \(n\) và \(S\) \((1 \le n \le 10^5, 1 \le S \le 10^{14})\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_i\) \((a_i \le |10^9|)\).
• Dòng thứ ba chứa \(n\) số nguyên \(b_i\) \((b_i \le |10^9|)\).

Output

Gồm một dòng duy nhất là tổng số lượng đoạn nhạc thỏa mãn.

Example

3 5
1 2 3
7 1 10

4

Scoring

• Subtask 1 (\(30\%\) điểm): \(n \le 100, S \le 10^{14}, 0\le a_i, b_i \le 10^5\).
• Subtask 2 (\(40\%\) điểm): \(n \le 5000, S \le 10^{14}, |a_i|, |b_i| \le 10^7\).
• Subtask 3 (\(30\%\) điểm): Không có ràng buộc gì thêm.

Sau tất cả, Koruto muốn tránh mặt cô ấy càng nhiều càng tốt. Nhưng khổ nỗi cả hai lại học chung lớp, nên mỗi ngày vẫn phải di chuyển giữa cùng các tiết học.

Trong một ngày có \(n\) tiết học. Tiết học thứ \(i\) diễn ra ở phòng \(a_i\). Giữa các phòng có các hành lang hai chiều. Với mỗi cặp tiết liên tiếp \(i\) và \(i+1\), bạn được biết trước lộ trình mà cô ấy sẽ đi từ phòng \(a_i\) đến phòng \(a_{i+1}\).

Koruto muốn đi từ phòng \(a_i\) đến phòng \(a_{i+1}\) trong đúng cùng số bước với lộ trình đó, nhưng không được gặp cô ấy giữa đường.

Cụ thể, xét một lộ trình của cô ấy gồm \(L_i\) phòng:

với \(p_1 = a_i\) và \(p_{L_i} = a_{i+1}\). Cô ấy xuất phát tại \(p_1\) ở thời điểm \(0\), sau mỗi giây phải đi qua đúng một hành lang sang một phòng kề, và đến \(p_j\) ở thời điểm \(j-1\). Koruto cũng xuất phát cùng lúc ở \(p_1\), cũng phải di chuyển qua đúng một hành lang sau mỗi giây, không được đứng yên, và phải đến \(p_{L_i}\) sau đúng \(L_i - 1\) giây.

Koruto được xem là tránh được cô ấy nếu tại mọi thời điểm nguyên \(t\) thỏa mãn \(0 < t < L_i - 1\), hai người không ở cùng một phòng. Việc cùng ở phòng xuất phát tại \(t = 0\) và cùng đến phòng đích tại \(t = L_i - 1\) được cho phép.

Hãy cho biết với từng cặp tiết liên tiếp, Koruto có thể chọn một lộ trình an toàn hay không.

Input

• Dòng đầu chứa hai số nguyên \(n\) và \(m\) lần lượt là số tiết học và số phòng.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) là phòng học của từng tiết.
• Dòng thứ ba chứa số nguyên \(k\) là số hành lang.
• \(k\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) cho biết có hành lang hai chiều nối hai phòng \(u\) và \(v\).
• Sau đó là \(n-1\) nhóm dòng. Nhóm thứ \(i\) mô tả lộ trình của cô ấy từ \(a_i\) đến \(a_{i+1}\):
  • Dòng đầu chứa số nguyên \(L_i\).
  • Dòng tiếp theo chứa \(L_i\) số nguyên \(p_1, p_2, \dots, p_{L_i}\).

Output

• In ra \(n-1\) dòng. Dòng thứ \(i\) in YES nếu Koruto có thể đi an toàn từ \(a_i\) đến \(a_{i+1}\), ngược lại in NO.

Constraints

• \(2 \le n \le 5000\)
• \(1 \le m \le 5000\)
• \(0 \le k \le 5000\)
• \(1 \le a_i \le m\)
• \(1 \le u, v \le m, u \neq v\)
• Không có hai hành lang trùng nhau.
• \(1 \le L_i\)
• Tổng tất cả \(L_i\) không vượt quá \(5000\).
• Với mỗi lộ trình \(p_1, \dots, p_{L_i}\):
  • \(p_1 = a_i\) và \(p_{L_i} = a_{i+1}\).
  • Hai phòng liên tiếp luôn có hành lang nối trực tiếp.
  • Các phòng trong cùng một lộ trình là đôi một khác nhau, tức lộ trình của cô ấy là một đường đi đơn.

Example

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

YES
NO

Subtasks

• Subtask 1 (30%): \(n, m, k\) và tổng \(L_i\) không vượt quá \(100\).
• Subtask 2 (30%): \(L_i \le 3\) với mọi \(i\).
• Subtask 3 (40%): Không có ràng buộc gì thêm ngoài ràng buộc chính.

...Cảm ơn anh vì thời gian qua đã bên cạnh em, giúp đỡ em từ việc học tập đến những chuyện trong cuộc sống. Xin lỗi anh vì đã nhiều lần làm anh buồn và thất vọng. Thật lòng thì chuyện tụi mình dừng lại không hẳn là do ai sai cả, chỉ là em chưa sẵn sàng để bước thêm vào 1 mối quan hệ chính thức nào nữa. Em sợ khi lún quá sâu, rồi khi mình học khác trường, việc không thể gặp gỡ hay ở bên nhau thường xuyên, sự xa cách đó sẽ làm em khó buông bỏ hơn. Tụi mình cũng sắp ra trường rồi, mong anh giữ lại những kỉ niệm đẹp nhất về nhau và đừng buồn chuyện tụi mình nữa. Mong anh hiểu rằng, thời gian qua tình cảm và sự quan tâm em dành cho anh là chân thật nhất, không chút dối lừa nào cả. Cảm ơn anh vì tất cả những gì đã qua...

Cầm trên tay những dòng chữ ngay ngắn, nước mắt của Koruto chợt lăn xuống từng dòng... Cất vội bức thư tay vào hộp cùng với những lá thư viết cho nhau, anh đâu thể ngờ tới sự thật nghiệt ngã này... Mới đây thôi, em còn nói sẽ cho anh một số \(n\) mà, sao chưa em đã vội đi rồi ? Biết là \(m\) thằng trong qua khứ đã làm thương tổn em rất nhiều, anh nhớ rõ tên từng thằng mà, vì khi em buồn lúc nào cũng kể với anh hết, nhưng anh không ngờ nỗi đau giam giữ em sâu đến thế, vậy mà anh chẳng thể chữa lành cho em. Sau \(k\) ngày bên nhau, sao mọi thứ lại kết thúc nhanh vậy chứ ? Những lần nắm tay chuyện trò cùng em, mình từng hứa với nhau bao điều, bây giờ lại thành ra như vầy. Thôi đành cất nỗi buồn này vào trong, gói lại \(p\) kí ức đẹp đẽ nhất của hai ta và cất vào 1 góc trong tim, anh biết mình sẽ khó có thể quên em được rồi. Tình yêu anh dành cho em sẽ mãi như vậy, và khi em quay lại nhìn sẽ luôn có anh đứng đợi ở đó, nhưng chỉ tiếc là giờ thì 2 ta đã không còn chung đường nữa rồi. Mong sao em sẽ luôn hạnh phúc khi không còn anh ở bên cạnh, vì "ai cũng phải bắt đầu từ đâu đó" mà...

Bất chợt điện thoại rung lên, Koruto mở ra và thấy những dòng tin của ngài Tiến Sĩ Đá: "Kết thúc rồi sao ? Koruto có ổn không ?". Ting ting, lại thêm một tin nhắn từ một thằng bạn thân khác: "Còn luỵ không ? Tình hình sao rồi ?". Tình hình ấy à ? Ổn không ấy à ? Chắc là không rồi. Anh yêu cô ấy rât nhiều. Có lẽ anh sẽ chẳng có thể bao giờ quên được cô ấy. Lần đầu tiên có người con gái đem lại cho anh ấm áp như này. Nhưng giờ cô ấy đi rồi, chỉ còn lại anh cô đơn trong phòng cùng những mảnh kỉ niệm đẹp nhưng khi nhớ lại thì buồn. Đằng này mà có bị nói là simp lỏ thì anh cũng chịu thôi. Tưởng như sắp quên được rồi, nhưng mới hôm qua anh vẫn mơ thấy cô ấy. Vẫn đôi mắt ấy, vẫn cái miệng hay nhõng nhẽo, quan tâm và hỏi han anh, vẫn là mái tóc dài ấy, mới lúc trước còn trong vòng tay anh, nhưng giờ sao mà xa quá. Biết là nếu không níu giữ em, thì suốt đời sẽ đánh mất, nhưng anh đành buông tay thôi. Biết đâu, sau này khi cả hai ta đã trưởng thành và chín chắn hơn, vòng đời sẽ lại đẩy đưa, cho ta gặp lại nhau thêm một lần nữa ? Nếu có lúc đó, anh chắc chắn sẽ giữ tay em thật chặt, chẳng buông ra nữa...

Koruto cất dọn những tấm thiệp, những mẩu thư vào một cái hộp, bất chợt nhận ra phía sau bức thư còn có những dòng chữ viết rất vội :

¿¿¿±¾¾¾±À±¾¿±À±¿±¾¾±À±¿¿¿¿±¿¿¾±¿¾±À±¾¿¾¿±¿¿¿¿±¾¾¾±À±¿¾±¾¿±¿¿¿¿±À±¾¿¾¿±¿¿¿¿±¿¿±¾¿±¿¿¿¿±À±¾¿¿¿±¿¾±¾¿±¾¾¿±À±¾¿±¿¿¿¿±¿¿¾±¾¿±¾¾¿±À±¾¿±¾¾¿±¿¿¾±¾¾¾±¿¿±À±¾¿¾¿±¿¿¾±À±¾¿¾¿±¿¿¾±¿¾±À±¿±¾¾±À±¾¿¾¿±¾¾¾±¾¿±¾¾¿±À±¿¿¿¾±¾¾¾±¿¿±À±¿¿¿±¾¾¾±À±¾¿±¾¾¿±¿¾±¾¿¾¾±À±¾±¿¿¾±¿¿±À±¾¾±¿¿±¾¿±¿¿¿¿±À±¾¿¿¿±¿±¾¿±À±¾¿±¿¿¿¿±¿¾±¿¿¾±À±¾¿±¿¿¿¿±¿¾±¾¿±À±¿¿¿¾±¾¾¾±¿¿±À±¾¿¿¿±¿¿±¾¿±¿¿¿¿±À±¿¾¾¿±¿¿¿¿±¿¿¾±¾¾¾±¾¿±¾¾¿±À±¾¿±¿¿¿¿±¿¿¾±¾¿±¾¾¿±À±¾¿¾±¿¿±À±¾¿±¿¿±¿±¾¾

Key: 1 số có 3 chữ số nào đó...

Xem ra cô ấy vẫn còn có những điều muốn nhắn nhủ...

Input

• Cái gì đó

Output

• Cái gì đó

Example

something

nah

**Hint: ** hãy đọc và giải bài Mã hóa tin nhắn trước