Bài tập

Mark là CEO của tập đoàn Space X, sau khi ông tổ chức cho nhân viên của tập đoàn đi du hành vũ trụ về, ông thực hiện dự án mới đó là nghiên cứu một loại mảnh ghép mới để lắp ghép ra các thiết bị không gian có độ dài tùy ý. Loại mảnh ghép này dùng một loại vật liệu mới rất cứng nên không thể cắt hàn như các vật liệu thông thường, nó dùng các ngàm âm dương để liên kết với nhau. Để thuận tiện cho việc lắp ghép các thiết bị, tập đoàn đã sản xuất sẵn \(n\) mảnh ghép, mỗi mảnh ghép có chiều dài nhất định; người ta căn cứ vào chiều dài thiết bị của mình để lấy số lượng các mảnh ghép phù hợp. Chiều dài của thiết bị sau lắp ghép chính là tổng chiều dài của các mảnh ghép được sử dụng.

Một thiết bị có chiều dài \(d\) được gọi là lắp ghép được nếu tồn tại cách chọn các mảnh ghép của từng loại sao cho tổng chiều dài đúng bằng \(d\).

Các thiết bị này sẽ được sử dụng trên các trạm không gian, mỗi trạm có một giới hạn chiều dài \(T\) nhất định. Để đánh giá sự linh hoạt về chiều dài của các mảnh ghép này, người ta tiến hành xem xét có thể lắp ghép được những thiết bị có độ dài bao nhiêu trong khoảng giới hạn của trạm (tức là giới hạn trong đoạn \([0,T]\)).

Hãy giúp Mark thống kê số lượng các chiều dài \(d\) của thiết bị có thể lắp ghép được \((0 \le d \le T)\).

Input

Cho trong file LEGO.INP, có cấu trúc:

• Dòng 1: Chứa hai số nguyên dương \(n\) và \(T\) \((1 \le n \le 2000,\ 0 \le T \le 10^{18})\).
• Dòng 2: Chứa \(n\) số nguyên dương \(a_1,a_2,\ldots,a_n\) là chiều dài của từng mảnh ghép \((1 \le a_i \le 2000)\).

Các số trên cùng một dòng được ghi cách nhau bởi ít nhất một dấu cách.

Output

Ghi ra file LEGO.OUT:

• Dòng 1: Ghi một số nguyên duy nhất là kết quả của bài toán.

Example

2 7
2 5

6

Scoring

• 40% số test tương ứng với 40% số điểm có \(T \le 2\times10^3\).
• 20% số test tương ứng với 20% số điểm có \(T \le 2\times10^4\).
• 20% số test tương ứng với 20% số điểm có \(T \le 2\times10^5\).
• 20% số test còn lại có \(T \le 10^{18}\).

Mark là CEO của tập đoàn Space X, ông được phân công làm công tác tổ chức cho toàn bộ nhân viên của tập đoàn đi tham quan các trạm không gian. Tập đoàn có \(n\) nhân viên, nhân viên thứ \(i\) có mã số nhân viên là \(a_i\).

Mark sẽ chia nhân viên của tập đoàn thành 2 nhóm, nhóm A và nhóm B, mỗi nhóm cần ít nhất một nhân viên. Để tạo sự gắn kết giữa các thành viên, mỗi nhóm sẽ chọn một mã màu để đại diện cho nhóm mình, mã màu có giá trị trong khoảng từ \(1\) tới \(10^9\) sao cho mã màu được chọn sẽ nhỏ hơn hoặc bằng mã số nhỏ nhất của các thành viên trong nhóm. Hai cách chia được gọi là khác nhau nếu một nhân viên thuộc một nhóm khác hoặc có một mã màu khác trong hai cách chia.

Hãy giúp Mark đếm số cách chia nhóm khác nhau cho kế hoạch của mình. Vì số cách chia có thể rất lớn, kết quả được ghi ra sau khi lấy modulo cho \((10^9+7)\).

Input

Cho trong file GROUP.INP, có cấu trúc:

• Dòng 1: Chứa số nguyên dương \(n\), là số nhân viên của tập đoàn \((2 \le n \le 10^5)\).
• Dòng 2: Chứa \(n\) số nguyên dương \(a_1,a_2,\ldots,a_n\), là mã số của các nhân viên \((1 \le a_i \le 10^9)\).

Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Output

Ghi ra file GROUP.OUT:

• Dòng 1: Ghi một số nguyên duy nhất là kết quả của bài toán.

Example

sample 2 1 2

sample 4

Với \(n=2\), \(a_1=1\) và \(a_2=2\):

    - Trường hợp 1: Nhóm A gồm $a_1=1$ (min=1) nên có 1 cách chọn mã màu; nhóm B gồm $a_2=2$ (min=2) nên có 2 cách chọn mã màu. Ta được $1 \times 2 = 2$ cách chia.
    - Trường hợp 2: Nhóm A gồm $a_2=2$ (min=2) có 2 cách chọn mã màu; nhóm B gồm $a_1=1$ (min=1) có 1 cách chọn mã màu. Ta được $2 \times 1 = 2$ cách chia.

    Tổng lại có 4 cách chia.

sample 2 2 3

sample 12

Với \(n=2\), \(a_1=2\) và \(a_2=3\):

    - Trường hợp 1: Nhóm A gồm $a_1=2$ (min=2) có 2 cách chọn màu; nhóm B gồm $a_2=3$ (min=3) có 3 cách chọn màu. Ta được $2 \times 3 = 6$ cách.
    - Trường hợp 2: Đổi vai trò nhóm A và B, ta được thêm 6 cách nữa.

    Tổng lại có 12 cách chia.

sample 3 1 2 3

sample 14

Với \(n=3\), \(a_1=1, a_2=2, a_3=3\). Các cách chia thành 2 nhóm tập hợp là:

    - $\{1\}$ và $\{2, 3\}$: Nhóm thứ nhất có min=1 (1 màu), nhóm thứ hai có min=2 (2 màu). Có $1 \times 2 = 2$ cách chọn màu. Hoán đổi A và B ta có $2 \times 2 = 4$ cách.
    - $\{1, 3\}$ và $\{2\}$: Nhóm thứ nhất có min=1 (1 màu), nhóm thứ hai có min=2 (2 màu). Tương tự có 4 cách.
    - $\{1, 2\}$ và $\{3\}$: Nhóm thứ nhất có min=1 (1 màu), nhóm thứ hai có min=3 (3 màu). Có $1 \times 3 = 3$ cách. Hoán đổi A và B ta có $3 \times 2 = 6$ cách.

    Tổng số cách chia: $4 + 4 + 6 = 14$ cách.

Scoring

• 40% số test tương ứng với 40% số điểm có \(n \le 20\).
• 40% số test tương ứng với 40% số điểm có \(n \le 30\) và \(a_i \le n\) với mọi \(i\).
• 20% số test tương ứng với 20% số điểm còn lại không có ràng buộc gì thêm.

Cho một xâu và một từ khóa, nhiệm vụ của bạn là đếm số lượng vị trí mà từ khóa xuất hiện trong xâu.

Input

• Dòng đầu vào đầu tiên có một xâu độ dài \(n\) và dòng đầu vào thứ hai có một từ khóa độ dài \(m\). Cả hai đều bao gồm các ký tự a - z.
• \(1 \leq n, m \leq 10^6\)

Output

• In một số nguyên: số lần xuất hiện.

Example

saippuakauppias
pp

2

Bob là một cư dân nổi tiếng của vương quốc Seesawia, một nơi huyền bí nơi mọi vật thể hoạt động dựa trên nguyên lý cân bằng tuyệt đối. Bob rất thích chơi bập bênh, và từ những ngày thơ ấu của mình, cậu đã có một niềm đam mê mãnh liệt với những chiếc bập bênh cân bằng. Mỗi ngày, Bob lại dành hàng giờ trên chiếc bập bênh kỳ diệu của mình, nghiên cứu cách làm thế nào để giữ cho nó không nghiêng về bất kỳ phía nào, luôn giữ trạng thái hoàn hảo giữa trái và phải.

Vào một ngày nọ, sau khi chơi xong, Bob đã nảy ra một bài toán liên quan đến mảng bập bênh cân bằng - một cấu trúc đặc biệt mà cậu tin rằng sẽ đóng vai trò quan trọng trong việc duy trì hòa bình và sự ổn định cho toàn vương quốc Seesawia. Cụ thể, Bob định nghĩa một mảng \(A = [a_1, a_2, \dots, a_m]\) là một mảng bập bênh cân bằng nếu như tồn tại một vị trí \(k\) giữa mảng (\(1 \leq k \leq m\)) sao cho:

\begincenter
$
\sum_{i=1}^{m} (i - k) a_i = 0
$
\endcenter

Điều này có nghĩa là nếu mỗi phần tử \(a_i\) của mảng được coi là một vật nặng đặt trên một chiếc bập bênh ở vị trí \(i\), thì sẽ có một điểm \(k\) mà tại đó bập bênh không bị nghiêng về phía trái hay phải.

Như một món quà sinh nhật, Bob đã nhận được một mảng \(A = [a_1, a_2, \dots, a_n]\) từ người bạn thân của mình, một thợ thủ công nổi tiếng trong vương quốc. Tuy nhiên, mảng này không cố định: nó có thể thay đổi theo thời gian khi có các yếu tố tác động từ môi trường. Bob muốn biết liệu có một đoạn con nào của mảng mà vẫn giữ được trạng thái cân bằng này sau những thay đổi đó không.

Bob đã phát hiện ra rằng các phần tử trong mảng có thể thay đổi theo thời gian thông qua ba loại phép biến đổi sau, và đây là lúc bạn cần giúp đỡ Bob:

• Loại 1 \(\ell\) r x: Trong một ngày nắng đẹp, Bob quyết định làm cho một đoạn con từ \(a_\ell\) đến \(a_r\) nặng hơn bằng cách thêm vào mỗi phần tử \(x\) đơn vị trọng lượng.
• Loại 2 \(\ell\) r x: Trong một cuộc hành trình đến đỉnh Seesaw, Bob đã khám phá ra một loại đá quý phép thuật. Với mỗi viên đá, Bob có thể làm thay đổi toàn bộ trọng lượng của một đoạn con từ \(a_\ell\) đến \(a_r\) thành một giá trị mới là \(x\).
• Loại 3 \(\ell\) r: Bob muốn kiểm tra xem liệu đoạn \([a_\ell, a_{\ell+1}, \dots, a_r]\) hiện tại có đang ở trạng thái cân bằng hay không. Nếu cân bằng, bạn hãy in ra "Yes", nếu không thì in ra "No".

Hành trình của Bob vẫn tiếp diễn khi cậu khám phá ra vô số cách thay đổi và tương tác với mảng, và mỗi lần thay đổi đều đòi hỏi sự khéo léo và nhanh nhạy trong việc duy trì sự cân bằng của vương quốc. Bạn hãy giúp Bob bằng cách giải quyết các truy vấn này thật nhanh chóng và chính xác nhé

Input

Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\). \(n\) là độ dài của mảng, và \(q\) là số lượng truy vấn.

Dòng thứ hai chứa \(n\) số nguyên \(a_i\) để biểu diễn mảng.

Mỗi truy vấn tiếp theo là một truy vấn được mô tả theo định dạng như sau:

• 1 $\ell$ r x: Tăng giá trị của đoạn \([a_\ell, a_{\ell+1}, \dots, a_r]\) thêm \(x\).
• 2 $\ell$ r x: Thay toàn bộ giá trị của đoạn \([a_\ell, a_{\ell+1}, \dots, a_r]\) thành \(x\).
• 3 $\ell$ r: Kiểm tra xem đoạn \([a_\ell, a_{\ell+1}, \dots, a_r]\) có cân bằng hay không.

Output

Đối với mỗi truy vấn loại 3, in ra "Yes" nếu đoạn \([a_\ell, a_{\ell+1}, \dots, a_r]\) là mảng bập bênh cân bằng, ngược lại in ra "No".

Example

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

Yes
No
Yes
Yes

Scoring

Trong tất cả các test :

• \(1 \leq n \leq 100\,000\): Độ dài của mảng.
• \(1 \leq q \leq 1\,200\,000\): Số lượng truy vấn mà Bob phải xử lý.
• \(-1000 \leq a_i \leq 1000\): Giá trị ban đầu của mỗi phần tử trong mảng \(A\).
• \(-10\,000 \leq x \leq 10\,000\): Giá trị của \(x\) trong mỗi phép biến đổi.
• Sau mỗi phép biến đổi, bạn có thể giả định rằng \(|a_i| \leq 1.5 \times 10^9\).
• \(1 \leq \ell \leq r \leq n\): Chỉ số của các đoạn con trong mỗi truy vấn.

Subtask \(1\) với \(20\%\) số điểm có \(n, q <= 200\).

Subtask \(2\) với \(20\%\) số điểm có \(n, q <= 2000\).

Subtask \(3\) với \(20\%\) số điểm trong \(q\) truy vấn, không có truy vấn loại \(1\).

Subtask \(4\) với \(20\%\) số điểm trong \(q\) truy vấn, không có truy vấn loại \(2\).

Subtask \(5\) với \(20\%\) số điểm còn lại không có ràng buộc gì thêm.