TaThanHungbc là một lập trình viên tài ba. Thành tựu về lập trình của anh thật sự rất đáng ngưỡng mộ, tiêu biểu là thuật toán $\mathtt{\text{luồng LogN}}$(đưa mọi bài toán về luồng và giải quyết chúng với độ phức tạp $\mathtt{\text{O(Log N)}}$), $\mathtt{\text{công nghệ nhập xuất tiên tiến}}$ (nhập xuất file trên ${10}^9$ số với độ phức tạp $\mathtt{\text{O(1)}}$)...

Gần đây anh đã nghiên cứu(tự nghĩ) một vài mã dữ liệu cho thuật toán mới của anh. Tuy nhiên, một vài chuyên gia nhận định rằng những mã dữ liệu này khá dài dòng và cần được rút gọn bởi vì: $\mathtt{\text{"Code càng ngắn thì càng tối ưu"}}$. Anh nhận thấy rằng những kí tự liên tiếp giống nhau hoàn toàn có thể lược bỏ bớt còn lại $1$ hoặc $2$ kí tự (có thể không xóa kí tự nào) thì mã dữ liệu này vẫn hoạt động tốt.

Ngoài việc tối ưu mã dữ liệu này, anh còn quan tâm đến có bao nhiêu cách rút gọn mã dữ liệu. Vì còn bận rộn với rất nhiều thuật toán khác nhau, bạn hãy giúp TaThanHungbc thực hiện việc này.

$\mathtt{\text{Input}}$

• Dòng đầu tiên chứa xâu $S$ mô tả đoạn mã dữ liệu.

$\mathtt{\text{Output}}$

• Gồm một số nguyên duy nhất là số cách tối ưu mã dữ liệu (lược bỏ các kí tự ở vị trí khác nhau là cách tối ưu khác nhau).
• Vì kết quả có thể rất lớn nên hãy in ra phần dư khi chia cho $\mathtt{\text{998244353}}$.

$\mathtt{\text{Constraint}}$

• $1\le |S|\le {10}^6$

$\mathtt{\text{Subtask}}$

• Subtask $1$ ($50\mathrm{\%}$ số điểm): Đoạn mã dữ liệu ban đầu đã được tối ưu (TaThanHungbc cực kì khủng).
• Subtask $2$ ($50\mathrm{\%}$ số điểm): Không có giới hạn gì thêm (TaThanHungbc vẫn cực kì khủng nhưng muốn đặt ra thách thức cho bạn).

$\mathtt{\text{Sample Input 1}}$

aabb

$\mathtt{\text{Sample Output 1}}$

9

$\mathtt{\text{Sample Input 2}}$

xxzzzz

$\mathtt{\text{Sample Output 2}}$

30

$\mathtt{\text{Notes}}$

$\mathtt{\text{Sample Test 1}}$

• aabb
• $$a$$abb
• a$$a$$bb
• aa$$b$$b
• $$a$$a$$b$$b
• a$$ab$$b
• aab$$b$$
• $$a$$ab$$b$$
• a$$a$$b$$b$$

Thành phố $\mathtt{\text{X}}$ có dạng lưới $N\times M$. Mỗi ô của lưới là một khu vực.

CodeTN là một kẻ lang thang muốn đi qua thành phố này. CodeTN phải đi từ ô $(1,0)$ đến ô $(1,1)$ để đi vào, và $(N,M)$ đến ô $(N,M+1)$ để thoát khỏi thành phố.

Tuy nhiên hệ thống giao thông ở đây lại rất nghiêm ngặt. Khi muốn đi từ khu vực này sang khu vực khác, người tham gia giao thông chỉ được di chuyển theo hướng mà mình đang đi(kể cả khi đi vào hay đi ra khỏi thành phố). Có $K$ trạm đổi hướng giúp người tham gia giao thông có thể đổi hướng hiện tại sang $4$ hướng. Việc sử dụng trạm đổi hướng này sẽ tốn một lượng chi phí khá đáng kể.

Nhà lữ hành CodeTN rất muốn đi qua thành phố này lại còn muốn sử dụng một lượng ít trạm đổi hướng nhất. Bạn hãy giúp CodeTN tính toán việc chi tiêu này nhé!

$\mathtt{\text{Input}}$

• Dòng đầu tiên chứa hai số nguyên $N$, $M$ là kích thước của thành phố.

• Dòng thứ hai chứa số nguyên $K$ là số lượng của trạm đổi hướng.

• $K$ dòng tiếp theo mỗi dòng chứa hai số nguyên $X$, $Y$ là tọa độ của trạm đổi hướng ($1\le X\le N$, $1\le Y\le M$).

$\mathtt{\text{Output}}$

• Gồm một số nguyên duy nhất là số lượng trạm chuyển hướng ít nhất mà CodeTN cần dùng để đi qua thành phố này hoặc là $-1$ nếu CodeTN không thể đi qua thành phố này.

$\mathtt{\text{Constraint}}$

• $2\le N$,$M\le {10}^9$
• $1\le K\le min(N\times M,2\times {10}^5)$

$\mathtt{\text{Subtask}}$

• Subtask $1$ ($15\mathrm{\%}$ số điểm): $N=2$, $M\le 5\times {10}^3$.
• Subtask $2$ ($15\mathrm{\%}$ số điểm): $N\times M$ $\le 20$ .
• Subtask $3$ ($20\mathrm{\%}$ số điểm): $N$, $M$ $\le {10}^3$ .
• Subtask $4$ ($30\mathrm{\%}$ số điểm): $N$, $M$ $\le 2\times {10}^5$ .
• Subtask $5$ ($20\mathrm{\%}$ số điểm): Không có giới hạn gì thêm .

$\mathtt{\text{Sample Input}}$

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

$\mathtt{\text{Sample Output}}$

4

$\mathtt{\text{Notes}}$

Kì thi tốt nghiệp THPT năm 2024 đã trôi qua, báo hiệu sự kết thúc 12 năm học gian nan của lứa 2k6. heygnauq đã cùng bạn bè đi Đà Nẵng chơi một chuyến sau những ngày sống cùng sách vở.

Trong lúc tắm bồn ở khách sạn, heygnauq đã vô tình làm ở lỗ thoát nước mà không hề hay biết, cậu chỉ nhận ra lỗ thoát bị rò rỉ chỉ khi ngâm mình trong bồn tắm tĩnh lặng và đang nghĩ vu vơ về ai đó (hoặc về giáo án thầy Tu mù proxy cùng cô adc xúc tu). Bỗng chốc heygnauq nảy ra một ý tưởng, cậu thắc mắc liệu rằng có một bồn tắm có rất nhiều vòi nước và lỗ thoát nước cùng mở một lúc thì sau bao lâu, bồn tắm sẽ đầy hoặc cạn nước.

Vì quá bận đi chơi ($\mathtt{\text{LOL}}$) nên heygnauq đành nhờ bạn giải quyết vấn đề đó.

$\mathtt{\text{Input}}$

• Dòng đầu tiên chứa 2 số nguyên $n,m$ lần lượt là số vòi nước và số lỗ thoát nước.
• $n$ dòng tiếp theo, dòng thứ $i$ là thời gian vòi thứ $i$ chảy đầy bồn tắm không hở.
• $m$ dòng tiếp theo, dòng thứ $i$ là thời gian lỗ thứ $i$ rút hết nước trong bồn khi bồn đầy nước.
• Dòng cuối cùng chứa một hữu tỉ $t$ là lượng nước hiện tại trong bồn.
• Lưu ý:
  • Thời gian được cho dưới dạng giờ phút giây, ví dụ $9$ giờ $0$ phút $24$ giây sẽ được biểu diễn là $\mathtt{\text{9h0m24s}}$. Cụ thể hơn ở test ví dụ.
  • Nếu số hữu tỉ đó vô hạn tuần hoàn thì sẽ được cho dưới dạng như sau: Ví dụ $\mathtt{\text{0.8(83)}}$ trong đó $83$ chính là phần tuần hoàn.

$\mathtt{\text{Output}}$

• Dòng đầu tiên in ra $\mathtt{\text{FULL}}$ hoặc $\mathtt{\text{EMPTY}}$ khi mực nước trong bồn đầy hoặc cạn sau một khoảng thời gian.
• Dòng tiếp theo in ra một chuỗi ký tự có dạng $\mathtt{\text{P/Q}}$ trong đó $P/Q$ là số giờ để bồn đầy nước hoặc cạn nước dưới dạng phân số tối giản.

$\mathtt{\text{Sample Input}}$

2 3
7h30m0s
5h0m0s
10h0m0s
15h37m30s
7h48m45s
0.05(63)

$\mathtt{\text{Sample Output}}$

FULL
7785/341

$\mathtt{\text{Constraint}}$

• Thời gian của các vòi nước và lỗ thoát luôn bé hơn $1000$ giờ.
• $1\le n,m\le 100000$.
• $0<t<1$.

$\mathtt{\text{Subtask}}$

• Subtask $1(20\mathrm{\%})$: Thời gian của tất cả vòi và lỗ đều bằng nhau và đều có số phút, số giây bằng $0$; $t=0.5$.
• Subtask $2(30\mathrm{\%})$: Thời gian của tất cả vòi bằng nhau, thời gian của tất cả lỗ bằng nhau.
• Subtask $3(30\mathrm{\%})$: Dữ liệu đảm bảo $P,Q<{10}^{18}$.
• Subtask $4(20\mathrm{\%})$: Không có ràng buộc gì thêm.

Ông Q (heygnauq sau này) là một nhà du hành thời gian vĩ đại, sở hữu cho mình một cỗ máy thời gian toàn năng có thể thay đổi cả tương lai. Tuy nhiên, ông vẫn gặp khó khăn với công việc, bị deadline dí như bao người khác.

Công việc của ông Q là hiệu chỉnh một dãy $A$ gồm $n$ số nguyên ban đầu thành một dãy hoàn hảo nhất để ổng được thăng quan tiến chức. Vì thời gian gấp rút nên khi điều chỉnh đến khi nào thấy dãy no hope quá thì ông Q sẽ dùng cỗ máy thời gian quay về một thời điểm mà ông đã từng trải qua khi đang hiệu chỉnh (có thể bao gồm những dòng thời gian song song khác) để có thể chạy kịp deadline với một dãy $A$ hoàn hảo nhất có thể.

Vì dãy số $A$ có thể rất dài nên ông Q không thể kiểm tra và tính toán hết được, ông ta chỉ có thể nhờ bạn thực hiện truy vấn điều chỉnh dãy số hoặc kiểm tra một đoạn trên đó. Ngoài ra, bạn còn phải giúp ổng du hành thời gian đến thời điểm sau một truy vấn bất kì đã trải qua trước đó.

$\mathtt{\text{Input}}$

• Dòng đầu tiên gồm 2 số nguyên $n$ và $q$ lần lượt là số phần tử của dãy $A$ (các phần tử được đánh số từ $1$ tới $n$) và số truy vấn.

• Dòng tiếp theo chứa $n$ số nguyên lần lượt là $n$ phần tử của dãy $A$.

• $q$ dòng tiếp theo, dòng thứ $i$ chứa thông tin của truy vấn thứ $i$, một truy vấn có thể là:

  • $\mathtt{\text{C l r s}}$ $(1\le l\le r\le n)$: hiệu chỉnh tăng các phần tử từ $A_l$ đến $A_r$ lên $s$ đơn vị.

  • $\mathtt{\text{S l r}}$ $(1\le l\le r\le n)$: tính tổng của dãy con từ $A_l$ đến $A_r$.

  • $\mathtt{\text{B t}}$: du hành thời gian đến thời điểm sau truy vấn thứ $t$ (dữ liệu đảm bảo truy vấn này không thể quay về một truy vấn dạng $\mathtt{\text{B}}$ khác).

$\mathtt{\text{Output}}$

• Với mỗi truy vấn dạng $\mathtt{\text{S}}$, in ra một số nguyên duy nhất là tổng của dãy con $(l,r)$ trên một dòng, vì kết quả có thể lớn nên hãy in ra phần dư khi chia cho ${10}^9+7$.

$\mathtt{\text{Sample input}}$

7 6
1 1 1 1 1 1 1
C 2 6 1
C 3 5 1
B 0
S 2 7
B 2
S 2 5

$\mathtt{\text{Sample output}}$

6
11

$\mathtt{\text{Constraint}}$

• $1\le n\le {10}^5$.

• $1\le q\le {5.10}^4$.

• $1\le s,A_i\le 1000$.

$\mathtt{\text{Subtask}}$

• Subtask $1(10\mathrm{\%})$: Không có truy vấn dạng $\mathtt{\text{B}}$ và $n\le 1000$, $q\le 500$.

• Subtask $2(20\mathrm{\%})$: Không có truy vấn dạng $\mathtt{\text{B}}$.

• Subtask $3(30\mathrm{\%})$: $l=r$ trong tất cả truy vấn dạng $\mathtt{\text{C}}$.

• Subtask $4(40\mathrm{\%})$: Không có giới hạn gì thêm.

$\mathtt{\text{Notes}}$

• Ban đầu ông Q có dãy $A=(1,1,1,1,1,1,1)$.

• Sau truy vấn $1$, dãy trở thành $(1,2,2,2,2,2,1)$.

• Sau truy vấn $2$, dãy trở thành $(1,2,3,3,3,2,1)$.

• Truy vấn $3$ yêu cầu ta du hành thời gian đến thời điểm ban đầu, khi dãy $A$ là $(1,1,1,1,1,1,1)$.

• Truy vấn $4$ yêu cầu in ra tổng của dãy con từ $A_2$ tới $A_7$: $1+1+1+1+1+1=6(\mathtt{\text{mod}}{10}^9+7)$.

• Truy vấn $5$ yêu cầu ta du hành về thời điểm sau truy vấn $2$, tức là dãy $(1,2,3,3,3,2,1)$.

• Truy vấn cuối cùng yêu cầu in ra tổng của dãy con từ $A_2$ tới $A_5$: $2+3+3+3=11(\mathtt{\text{mod}}{10}^9+7)$.

Đây là một bài toán $\mathtt{\text{function-grading}}$.

Trong kỳ thi $\mathtt{\text{TST 2024}}$, admin $\mathtt{\text{LamTer}}$ đã đạt top $16$ (thiếu đúng $5$ để đạt được giấc mơ $\mathtt{\text{APIO}}$). Trong kỳ thi đó admin $\mathtt{\text{LamTer}}$ đã all-in bài $6$ (một bài $\mathtt{\text{function-grading}}$) nhưng bất thành. Thế nên hôm nay admin $\mathtt{\text{LamTer}}$ sẽ cho các bạn làm bài $6$ $\mathtt{\text{TST}}$ năm nay nhưng đề dễ hơn.

gaogao là chủ trì của một cuộc bỏ phiếu cấp cao gồm có $n$ cử tri bỏ phiếu tán thành hoặc không tán thành. Kết quả bỏ phiếu của từng cử tri được lưu lần lượt từ vị trí $1$ đến vị trí $n$ của một mảng $a$ độ dài $n+1$ được đánh số từ $0$ với giá trị $1$ có ý nghĩa là tán thành và ngược lại. gaogao cần phải xem kết quả chung cuộc của cuộc bỏ phiếu là tán thành hay không tán thành, một cuộc bỏ phiếu được coi là tán thành khi số phiếu tán thành nhiều hơn hẳn số phiếu không tán thành và ngược lại. Nhưng vì để giữ tính khách quan của cuộc bỏ phiếu gaogao không được phép biết giá trị của mảng $a$ mà chỉ được thực hiện một số phép gán có dạng $a_k:=a_i\mathtt{\text{nand}}{a}_j$. Sau cùng kết quả của cuộc bỏ phải được lưu vào vị trí $a_0$ với giá trị $1$ tương ứng với tán thành và ngược lại.

Phép $\mathtt{\text{nand}}$ được định nghĩa như sau:

Bạn hãy giúp gaogao thực hiện nhiệm vụ này.

$\mathtt{\text{Implementation}}$

Thí sinh cần cài đặt hàm sau:

void solve(int n);

Sau khi thực hiện hàm solve thì vị trí $a_0$ phải chứa kết quả của cuộc bầu cử, các vị trí khác không quan trọng.

Ngoài ra thí sinh có thể gọi tới hàm sau đây một số lần tùy ý:

void nandbit(int i, int j, int k);

Hàm nãy sẽ thực hiện phép gán $a_k=a_i\mathtt{\text{nand}}{a}_j$ ($0\le i,j,k\le n$).

Lưu ý: file của thí sinh cần phải cài đặt mà không có hàm main, phải khai báo thư viện #include "apiodream.h" và tuyệt đối không được tương tác với luồng ra vào chuẩn.

$\mathtt{\text{Scoring}}$

Với mỗi test:

• Nếu dãy $a$ sau khi thực hiện không đúng với yêu cầu hoặc bạn tương tác với luồng ra vào chuẩn hoặc bạn gọi hàm nandbit sử dụng các tham số không hợp lệ, bạn sẽ nhận được $0\mathrm{\%}$ điểm test đó và bị $\mathtt{\text{LamTer}}$ bonk đầu.
• Nếu dãy $a$ sau khi thực hiện đúng chính xác với yêu cầu, bạn sẽ nhận được $100\mathrm{\%}$ điểm test đó và gaogao bị $\mathtt{\text{LamTer}}$ bonk đầu.

$\mathtt{\text{Constraint}}$

• $2\le n\le 100$.

$\mathtt{\text{Contest Material}}$

#include <bits/stdc++.h>

void solve(int n);
void nandbit(int i, int j, int k);