Bài tập

Khoảng cách Hamming giữa hai xâu là số vị trí mà tại đó, kí tự ở hai xâu là khác nhau; trong lưu trữ và xử lí thông tin, người ta cũng đưa ra định nghĩa tương tự cho các số nhị phân: Khoảng cách Hamming giữa hai số nhị phân là số vị trí mà tại đó, trạng thái của hai bit ở hai số là khác nhau.

Cho hai dãy số nguyên không âm có cùng kích thước \(n\) : \(a_{1},a_{2},...,a_{n}\) và \(k_{1}, k_{2}, ..., k_{n}\) . Một dãy số \(i_{1}, i_{2},...,i_{k}\) gọi là đẹp nếu:

• \(1 \leq i_{1} < i_{2} < ... < i_{k} \leq n\)
• Khoảng cách Hamming giữa \(a_{i_{j}}\) và \(a_{i_{j−1}}\) đúng bằng \(k_{i_{j}}\) với mọi \(j\): $ 2 \leq j \leq k$

Hiện tại Quân đang thấy khó khăn khi phải tìm dãy số đẹp có kích thước lớn nhất.

Yêu cầu: Bạn hãy giúp Quân tìm dãy số đẹp có kích thước lớn nhất nhé.

Input

Dòng đầu tiên chứa số nguyên dương \(n\) \((n \leq 10^5)\)

Dòng thứ hai chứa \(n\) số nguyên \(a_{1},a_{2},...,a_{n}\) \((0 \leq a_{i} \leq 10^6)\)

Dòng thứ ba chứa n số nguyên \(k_{1}, k_{2}, ..., k_{n}\) \((0 \leq k_{i} \leq 10^6)\)

Output

In ra một số nguyên duy nhất là kích thước của dãy số đẹp tìm được.

Example

4
1 2 3 4
10 0 1 0

2

2
8 9
20 0

1

5
5 3 5 3 5
10 1 20 1 20

1

Scoring

Có \(20\%\) số điểm với \(n \leq 15\)

Có \(25\%\) số điểm với \(n \leq 5000\)

Có \(25\%\) số điểm với \(a_{1},a_{2},...,a_{n} \leq 1000\)

Còn lại không có điều kiện gì thêm

Bạn đang làm việc với một mạng lưới các thành phố bí ẩn, mỗi thành phố được tô bằng một màu nhất định. Ban đầu, tất cả các thành phố hoàn toàn bị cô lập, chưa có con đường nào nối giữa chúng. Tuy nhiên, theo thời gian, bạn có thể xây dựng các con đường để kết nối các thành phố và khám phá thêm thông tin về chúng.

Bạn được cung cấp \(q\) truy vấn, mỗi truy vấn thuộc một trong hai loại sau:

• Loại 1 \((1 \ u \ v)\): Xây dựng một con đường mới giữa hai thành phố \(u\) và \(v\), giúp mở rộng mạng lưới giao thông.

• Loại 2 \((2 \ u \ c)\): Điều tra thành phố \(u\) để tìm ra số lượng thành phố có màu \(c\) trong thành phần liên thông chứa \(u\).

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(q\) \((1 \leq n \leq 10^5, 1 \leq q \leq 2 \times 10^5)\) --- số thành phố và số truy vấn.

• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) \((1 \leq a_i \leq n)\), mỗi số mô tả màu sắc của thành phố thứ \(i\).

• \(q\) dòng tiếp theo, mỗi dòng chứa một truy vấn thuộc một trong hai loại:

• Truy vấn loại \(1\) có dạng \(1 \ u \ v\) \((1 \leq u, v \leq n, u \neq v)\), biểu thị việc xây dựng một con đường giữa \(u\) và \(v\).

• Truy vấn loại \(2\) có dạng \(2 \ u \ c\) \((1 \leq u, c \leq n)\), yêu cầu đếm số lượng thành phố có màu \(c\) trong thành phần liên thông chứa \(u\).

Output

• Với mỗi truy vấn loại \(2\), in ra một số nguyên trên một dòng duy nhất --- số lượng thành phố có màu \(c\) trong thành phần liên thông chứa \(u\) tại thời điểm truy vấn.

Example

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

1
0
3
1

Scoring

• \(1 \leq n \leq 10^5\)
• \(1 \leq q \leq 2 \times 10^5\)
• \(1 \leq a_i \leq n\)
• \(1 \leq u, v, c \leq n\)

Vào ngày Quốc tế Thiếu nhi, một đứa trẻ đã đến nhà của Picks và làm rối tung mọi thứ. Picks rất tức giận, bởi nhiều vật quan trọng đã biến mất, trong đó có dãy số yêu thích của anh ấy.

May mắn thay, Picks vẫn nhớ cách khôi phục lại dãy số. Ban đầu, anh ấy tạo ra một mảng số nguyên \(a[1], a[2], \ldots, a[n]\). Sau đó, anh ấy thực hiện \(m\) thao tác trên mảng này. Mỗi thao tác có thể là một trong ba loại sau:

• In tổng: 1 l r --- Picks muốn biết tổng các phần tử trong đoạn từ \(l\) đến \(r\) (tức là \(\sum\limits_{i=l}^{r} a[i]\)).
• Lấy dư: 2 l r x --- Với mỗi \(i\) trong đoạn \([l, r]\), thay \(a[i]\) bằng \(a[i] \bmod x\).
• Gán giá trị: 3 k x --- Gán giá trị \(a[k] := x\).

Bạn hãy giúp Picks thực hiện tất cả các thao tác, và in ra đáp án tương ứng với các thao tác loại 1.

Input

• Dòng đầu tiên chứa hai số nguyên \(n, m\) \((1 \le n, m \le 10^5)\) --- số phần tử ban đầu và số thao tác cần thực hiện.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((1 \le a_i \le 10^9)\) --- các phần tử ban đầu của mảng.

• Mỗi dòng trong số \(m\) dòng tiếp theo là một thao tác, theo một trong các định dạng sau:

• 1 $l$ $r$ \((1 \le l \le r \le n)\) --- thao tác loại 1 (in tổng đoạn).

• 2 $l$ $r$ $x$ \((1 \le l \le r \le n, 1 \le x \le 10^9)\) --- thao tác loại 2 (lấy dư đoạn).
• 3 $k$ $x$ \((1 \le k \le n, 1 \le x \le 10^9)\) --- thao tác loại 3 (gán giá trị tại vị trí).

Output

Với mỗi thao tác loại 1, in ra một dòng chứa tổng các phần tử trong đoạn tương ứng. Chú ý: Tổng này có thể vượt quá giới hạn của số nguyên 32-bit.

Example

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

8
5

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

49
15
23
1
9

Scoring

• Có \(30\%\) số điểm có \(n, m \leq 1000\).
• Có \(30\%\) số điểm trong các test không có truy vấn loại \(2\).
• \(40\%\) số điểm không có ràng buộc gì thêm.

Một dãy gồm \(n\) số nguyên \(a_{1}, a_{2},..., a_{n}\) được viết thành một hàng ngang, giữa hai số liên tiếp có một khoảng trắng, như vậy có tất cả \((n-1)\) khoảng trắng. Người ta muốn đặt \(k\) dấu cộng và \((n-1-k)\) dấu trừ vào \((n-1)\) khoảng trắng đó để nhận được một biểu thức có giá trị lớn nhất.

Ví dụ, với dãy gồm \(5\) số nguyên \(28, 9, 5, 1, 69\) và \(k = 2\) thì cách đặt \(28+9-5-1+69\) là biểu thức có giá trị lớn nhất.

Yêu cầu: Cho dãy gồm \(n\) số nguyên \(a_{1}, a_{2},..., a_{n}\) và số nguyên dương \(k\), hãy tìm cách đặt \(k\) dấu cộng và \((n-1-k)\) dấu trừ vào \((n-1)\) khoảng trắng để nhận được một biểu thức có giá trị lớn nhất.

Input

Dòng đầu chứa hai số nguyên dương \(n, k (k < n)\)

Dòng thứ hai chứa n số nguyên \(a_{1}, a_{2},..., a_{n}\) \((|a_{i}| ≤ 10^6)\)

Output

Một số nguyên là giá trị của biểu thức đạt được.

Example

5 2
28 9 5 1 69

100

Scoring

\(60\%\) số test có \(n \leq 20\).

\(40\%\) số test còn lại có \(n \leq 10^5\).