Thầy Lực bắt đầu bài giảng cho các SV nhập môn thuật toán của CLB H3.2PL. Thầy yêu cầu các bạn viết một dãy số lần lượt theo thứ tự sau: 1 số 1 rồi 2 số 2 rồi 3 số 3 rồi 4 số 4, 5 số 5, cứ thế, các bạn phải viết đến 500 ngàn số thì dừng.

~(1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,...)~

Tiếp đến, anh yêu cầu tính tổng của các số nguyên trong dãy số trên từ số nguyên thứ nhất đến số nguyên thứ ~K~. Chẳng hạn tổng của ba số nguyên dương đầu tiên là: ~1+2+2 = 5~. Bạn Long là một học viên của CLB, bạn duyệt trực tiếp để giải bài này. Thầy Lực cũng miễn cưỡng chấp nhận, nhưng thầy muốn xem thử có bạn nào giải tốt hơn hay không.

Input

Một số nguyên dương ~K~ duy nhất không quá ~5.10^5.~

Output

Kết quả của bài toán.

Sample input

2

Sample output

3

Chưng và Quýt là hai người bạn thân, cùng nhau khám phá thế giới kỳ lạ của Kiệt, nơi mọi thứ đều được mã hóa bằng những chuỗi nhị phân chỉ gồm 0 và 1. Một ngày nọ, Kiệt đưa cho họ một dãy ký tự nhị phân dài n và đặt ra cho hai bạn một thử thách không hề đơn giản. Bên cạnh dãy ký tự ấy, Kiệt còn đưa ra q câu hỏi, mỗi câu hỏi là một đoạn liên tiếp [l, r] trong dãy.

Với mỗi đoạn được hỏi, Chưng và Quýt phải cùng nhau quan sát tất cả các đoạn con nằm hoàn toàn trong đoạn [l, r]. Kiệt gọi một đoạn con là đẹp nếu trong đó số lượng bit 1 bằng đúng số lượng bit 0.

Nhiệm vụ của hai bạn là: Với mỗi truy vấn, hãy tính tổng độ dài của tất cả các đoạn con đẹp trong đoạn [l, r].. Thử thách này không hề dễ dàng, bởi Kiệt đưa ra những giới hạn rất lớn, là một người bạn của hai người bạn hãy giúp họ giải quyết bài toán này nhé!!

Input

• Dòng đầu tiên gôm hai số ~n~ và ~q~ với (~\leq n, q \le2e5 ~) là độ dài chuỗi và số lượng truy vấn.
• ~q~ dòng tiếp theo mỗi dòng gồm hai số ~[l, r]~ với (~1\leq l \leq r \leq n~)

Output In ra ~q~ dòng, mỗi dòng chứa một số nguyên là kết quả sau mỗi truy vấn

Subtask

Sample Input 1

6 3
101001
3 6
5 6
1 6

Sample Output 1

8
2
22

Giải thích:

Ở truy vấn [3, 6] ta sẽ có những đoạn đẹp là đoạn [3, 4], [5, 6] và [3, 6] tổng độ dài 3 đoạn này là: 2 + 2 + 4 = 8

Trong đêm Giao Thừa khi trăng tròn tỏa sáng và mọi người tin rằng vận mệnh có thể được thay đổi, quốc vương Thiên Ban đã mời đến một pháp sư Quýt để mở ra một nghi lễ cổ xưa mang tên Phép Đổi Vận.

Nghi lễ này sử dụng hai dãy số linh thiêng là ~a~ và ~b~, mỗi dãy gồm ~n~ phần tử, được đánh số từ ~1~ đến ~n~. Mỗi con số trong dãy tượng trưng cho một luồng vận khí khác nhau trong năm mới. Để hoàn thành nghi lễ, pháp sư Quýt cần tạo ra một dãy mới ~c~, trong đó mỗi phần tử ~c_i~ thể hiện sức mạnh vận mệnh tại vị trí ~i~.

Cụ thể, giá trị ~c_i~ được xác định như sau: ~c_i = \sum a_j \times b_k~ với tất cả các cặp chỉ số ~(j, k)~ thỏa mãn: ~j | k = i~ (tức là ~j~ và ~k~ là or bit của chúng lại bằng ~i~).

Do dịp tết cận kề nên ai cũng nôn nóng đi chơi nên bạn hãy trợ giúp pháp sư tính toán toàn bộ dãy ~c~ để hoàn tất nghi lễ Đổi Vận Đầu Năm cho vương quốc của Thiên Ban nhé.

Input

• Dòng đầu tiên chứa một số nguyên ~n~ với ~(1 \leq n \leq 10^5)~
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ với (~1\leq a_i \leq 10^5~)
• Dòng thứ ba chứa ~n~ số nguyên ~b_1, b_2, \dots, b_n~ với (~1\leq b_i \leq 10^5~)

Output

In ra ~n~ số nguyên, trong đó số thứ ~i~ là giá trị của ~c_i~.

Subtask

Sample Input

4
2 0 2 5
2 0 2 6

Sample Output

4 0 12 30

Tại vương quốc Tina trong những ngày Tết Nguyên Đán, khi đèn lồng đỏ treo khắp phố và pháo hoa rực sáng bầu trời đêm, cậu bé Chưng nhận được một món quà đầu năm vô cùng đặc biệt, một bộ Lego Lễ Hội dùng để xây nên bức tường may mắn cho năm mới.

Bộ Lego gồm ~n~ khối, mỗi khối mang một màu riêng biệt. Khối thứ ~i~ có màu ~i~, tượng trưng cho từng mảnh ghép vận may. Chưng quyết định xây dựng một bức tường trên một hàng đế thẳng gồm ~k~ vị trí, được đánh số từ ~1~ đến ~k~.

Việc xây dựng bức tường trên Tina tuân theo một nghi thức truyền thống đầu xuân:

• Trước tiên, Chưng đặt khối Lego màu ~1~ vào một vị trí bất kỳ trên hàng đế.
• Sau đó, với mỗi khối tiếp theo từ màu ~2~ đến màu ~n~, Chưng phải đặt khối đó vào một vị trí liền kề với vị trí của khối vừa đặt trước đó (tức là vị trí bên trái hoặc bên phải).
• Nếu vị trí liền kề đã có sẵn các khối Lego, khối mới sẽ được xếp chồng lên trên, trở thành khối nằm trên cùng tại vị trí đó.

Sau khi hoàn thành bức tường chào xuân, Chưng ghi lại một chuỗi gồm ~k~ phần tử để lưu giữ kỷ niệm:

• Phần tử thứ ~i~ là màu của khối Lego nằm trên cùng tại vị trí ~i~.
• Nếu tại vị trí đó không có khối Lego nào, giá trị được ghi là ~0~.

Hai chuỗi được xem là khác nhau nếu tồn tại ít nhất một vị trí mà giá trị ghi lại là khác nhau.

Yêu cầu: Hãy giúp Chưng tính xem có bao nhiêu chuỗi khác nhau mà cậu có thể ghi lại sau khi hoàn thành việc xây dựng bức tường Lego ngày Tết.

Vì số lượng chuỗi có thể rất lớn, hãy in kết quả dưới dạng phần dư khi chia cho ~2026~.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~ với ~(2 \le n, k \le 5000)~ trong đó ~n~ là số khối Lego và ~k~ là số vị trí trên hàng đế.

Output

In ra một số nguyên duy nhất là số lượng chuỗi khác nhau mà Nam có thể ghi lại, lấy modulo ~2026~

Subtask

Sample Input

3 3

Sample Output

6

Giải thích

Ta sẽ có 6 dãy số được tạo ra khi đặt các khối leogo theo quy luật như trên là: (1 2 3), (3 2 0), (0 3 2) (3 2 1), (0 2 3), (2 3 0)

Cụ thể như hình trên đề bài (tôi biết là tôi vẽ đẹp mò :33 )

Bạn Mây cho một dãy gồm ~n~ số nguyên ~a_1, a_2, ... , a_n~ cho nhóm ~Zero-4~ gồm bốn bạn Anh, Long, Kiệt, Lực. Nhóm ~Zero-4~ muốn chọn ra trong đó 4 số bất kỳ của dãy có tổng bằng 0. Hai bộ số được gọi là khác nhau nếu tồn tại một ~i~ mà ~a_i~ tham gia vào một nhóm và không tham gia vào nhóm kia (không quan tâm thứ tự). Bạn Mây muốn đố bộ số khác nhau có thể mà nhóm ~Zero-4~ chọn được; nhưng nhóm bạn ngoài cách duyệt vét cạn thì chưa có cách nào hợp lý. Mời các bạn cùng thử sức

Input

Dòng đầu tiên chứa số nguyên ~n~ với ~1 ≤ n ≤ 500~, dòng thứ 2 chứa các số ~a_1, a_2,..., a_n~ với ~-10^6 ≤ a_i ≤ 10^6, i = 1,2,...,n.~

Output

Kết quả của bài toán.

Sample input

6
-4 3 1 0 -2 5

Sample output

2