Bài tập

Alice là một kĩ sư đang làm việc trên một loại vi xử lí mới. Bộ vi xử lí làm việc trên tập số nguyên không âm \(S\) (các số có thể được xuất hiện nhiều lần) để mô phỏng sự sống trong Matrix. Ban đầu tập \(S\) là rỗng, bộ vi xử lí có các loại truy vấn sau:

• Truy vấn dạng: \(0\ x\), truy vấn này thêm một số nguyên \(x\) vào \(S\) (\(0 \le x \le 10^5\)). Nếu giá trị \(x\) đã có trong \(S\) thì truy vấn này vẫn được thực hiện;

• Truy vấn dạng: \(1\ x\), truy vấn này xóa một số \(x\) khỏi \(S\) (\(0 \le x \le 10^5\)). Nếu giá trị \(x\) không thuộc \(S\) thì truy vấn này không cần làm gì. Nếu giá trị \(x\) xuất hiện nhiều lần trong \(S\) thì truy vấn này chỉ xóa đi một lần;

• Truy vấn dạng: \(2\ a\), truy vấn này thay đổi cả tập \(S\) với sự ảnh hưởng của \(a\) (\(0 \le a \le 10^5\)). Cụ thể, với mỗi \(x\) thuộc \(S\), thay bằng \(x \oplus a\). Phép \(\oplus\) là phép toán \(XOR\).

• Truy vấn dạng: \(3\ k\), truy vấn này tính tổng \(k\) phần tử nhỏ nhất trong \(S\) (\(0 \le k \le |S|\)).

Để kiểm tra trước khi đưa vào sử dụng, Alice muốn bạn lập trình để xử lí chính xác các truy vấn trên.

Input

• Dòng đầu tiên chứa số nguyên dương \(Q\);
• Mỗi dòng trong \(Q\) dòng tiếp theo chứa hai số nguyên mô tả một truy vấn như trên. Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

Với mỗi truy vấn loại \(3\), in ra tổng của \(k\) phần tử nhỏ nhất trong \(S\) trên một dòng.

Example

6
0 1
2 2
0 3
3 2
2 2
3 1

6
1

Scoring

• Có \(25\) điểm thỏa mãn: \(Q \le 1000\);
• Có \(25\) điểm khác thỏa mãn: \(Q \le 10^5\) và không có truy vấn loại \(2\);
• Có \(25\) điểm khác thỏa mãn: \(Q \le 10^5\) và \(k \le 10\);
• Có \(25\) điểm còn lại thỏa mãn: \(Q \le 10^5\).

Có \(N\) chiếc đèn được xếp thành một hàng dài trong hành lang. Mỗi đèn chỉ có hai trạng thái: bật (1) hoặc tắt (0). Có một cơ chế đặc biệt cho phép bạn thay đổi trạng thái của một đoạn đèn bằng một trong ba thao tác sau:

• Chọn hai số nguyên \(p, q\) \((1 \le p \le q \le N)\), và tắt toàn bộ các đèn từ \(p\) đến \(q\).
• Chọn hai số nguyên \(p, q\) \((1 \le p \le q \le N)\), và bật toàn bộ các đèn từ \(p\) đến \(q\).
• Chọn hai số nguyên \(p, q\) \((1 \le p \le q \le N)\), và đảo trạng thái toàn bộ các đèn từ \(p\) đến \(q\) (nếu đèn đang bật thì tắt, nếu đang tắt thì bật).

Trạng thái hiện tại của các đèn được mô tả bởi chuỗi nhị phân \(A\) độ dài \(N\), trong đó ký tự thứ \(i\) là 0 nếu đèn thứ \(i\) đang tắt, và 1 nếu đang bật. Trạng thái mong muốn được mô tả bởi chuỗi nhị phân \(B\) độ dài \(N\).

Hãy tính số lượng thao tác ít nhất cần thực hiện để biến chuỗi \(A\) thành \(B\).

\InputFile

• Dòng đầu tiên chứa số nguyên \(N\) (\(1 \le N \le 10^5\)).
• Dòng thứ hai chứa chuỗi \(A\) gồm đúng \(N\) ký tự 0 hoặc 1.
• Dòng thứ ba chứa chuỗi \(B\) gồm đúng \(N\) ký tự 0 hoặc 1.

\OutputFile

In ra một số nguyên là số lượng thao tác tối thiểu để biến \(A\) thành \(B\).

\Scoring

• Subtask 1 (18%): \(N \le 18\)
• Subtask 2 (20%): \(N \le 2000\)
• Subtask 3 (16%): Chuỗi \(A\) chỉ gồm toàn ký tự 0
• Subtask 4 (46%): Không có ràng buộc bổ sung

\Examples

\beginexample
\exmp
8
11011100
01101001
4

\endexample

\Note

Một cách để thực hiện 4 thao tác như sau:

• Đảo đoạn [1, 4] \(\Rightarrow\) 00101100
• Bật đoạn [2, 2] \(\Rightarrow\) 01101100
• Đảo đoạn [6, 8] \(\Rightarrow\) 01101011.
• Tắt đoạn [6, 7] \(\Rightarrow\) 01101001

Không có cách nào thực hiện ít hơn 4 thao tác.

\endproblem

Cho một đồ thị vô hướng có \(N\) đỉnh và \(M\) cạnh. Sử dụng thuật toán DFS để duyệt qua đồ thị và đếm tổng số lượng thành phần liên thông (Connected Components) có trong đồ thị.

Input

• Dòng đầu tiên là hai số nguyên dương \(N\) và \(M\) (\(1 \leq N \leq 10^5, 0 \leq M \leq 10^5\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) mô tả một cạnh.

Output

Một dòng duy nhất chứa số lượng thành phần liên thông.

Example

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

2

Cho một đồ thị có hướng \(G=(V, E)\) gồm \(N\) đỉnh và \(M\) cung. Hai đỉnh \(s\) và \(t\) được cho trước. Một đường đi đơn là một dãy các đỉnh \(P=\langle p_0, p_1, \dots, p_k \rangle\) sao cho \(p_0=s\), \(p_k=t\), \((p_{i-1}, p_i) \in E\), và tất cả các đỉnh trên đường đi đều đôi một khác nhau.

Yêu cầu: Biết rằng tồn tại ít nhất một đường đi từ \(s\) tới \(t\), hãy tìm và chỉ ra đường đi đơn từ \(s\) đến \(t\) có thứ tự từ điển nhỏ nhất. Nếu không tồn tại đường đi, in ra -1.

Một đường đi \(P\) được coi là nhỏ hơn về thứ tự từ điển so với đường đi \(Q\) nếu tại chỉ số đầu tiên mà các đỉnh tương ứng khác nhau, đỉnh của \(P\) có chỉ số nhỏ hơn.

Input

• Dòng đầu tiên chứa bốn số nguyên \(N\), \(M\), \(s\), \(t\): số lượng đỉnh, số lượng cung, đỉnh xuất phát và đỉnh đích (\(1 \leq N \leq 10^5, 1 \leq M \leq 10^5, 1 \leq s, t \leq N\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa 2 số nguyên dương \(u, v\), thể hiện cho một cung nối từ đỉnh \(u\) đến đỉnh \(v\) trong đồ thị (\(1 \leq u, v \leq N\)).

Output

Ghi ra trên một dòng các đỉnh theo đúng thứ tự trên đường đi đơn giản có thứ tự từ điển nhỏ nhất tìm được, bắt đầu từ đỉnh \(s\) và kết thúc ở đỉnh \(t\), cách nhau một dấu cách. Nếu không tồn tại đường đi, in ra -1.

Example

8 11 1 8
1 2
2 3
2 4
3 1
7 5
3 7
4 6
6 2
5 8
1 8
6 4

1 2 3 7 5 8