Nguồn đề : https://codeforces.com/contest/1457/problem/A

Cho một ma trận game pacman hình chữ nhật gồm n hàng và m cột, tại mỗi ô của ma trận có một con ma hay còn gọi là ghost, pacman sắp đến nên để các ghost có thể tẩu thoát bạn đã tạo ra một lối thoát tại ô có tọa độ là (r,c), với 1 bước di chuyển các ghost có thể di chuyển từ ô đang ghost đang đứng (x,y) lên trên (x+1,y), xuống dưới (x-1,y), qua trái (x,y-1), qua phải (x,y+1) và không được đi ra ngoài ma trận, mỗi bước di chuyển như vậy tốn 1 giây. Hãy tính thời gian ngắn nhất để tất cả các ghost có thể tẩu thoát.

Input

Dòng đầu tiên chứa một số nguyên t - số lượng test ~(1 \le t \le 10^4 )~

t dòng tiếp theo, mỗi dòng chứa 4 số nguyên lần lượt là n, m, r, c ~(1 \le r \le n \le 10^9, 1 \le c \le m \le 10^9 )~

Output

Với mỗi test in ra thời gian ngắn nhất để tất cả các ghost có thể chạy thoát trên 1 dòng.

Sample Input 1

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

Sample Output 1

18
4
6

Nguồn đề : https://codeforces.com/contest/7/problem/D

Một chuỗi được gọi là k_meh nếu có đủ 3 điều kiện sau :

• Chính nó là một chuỗi palindrome.
• Gọi n là độ dài của chuỗi, ~ {\lfloor} n/2 {\rfloor} ~ kí tự đầu tạo thành một chuỗi (k-1)_meh
• ~ {\lfloor} n/2 {\rfloor} ~ kí tự cuối tạo thành một chuỗi (k-1)_meh

Đặc biệt, bất kì chuỗi nào cũng có thể là 0meh kể cả chuỗi rỗng, nhưng một chuỗi 0meh không thể là một chuỗi k_meh (k>0) và ngược lại.

Cho bạn một chuỗi s hãy tính tổng meh của tất cả các tiền tố của s.

Input

Chuỗi s, gọi n là độ dài của chuỗi ~(1 \le n \le 10^6 )~

Output

Cho bạn một chuỗi s hãy tính tổng meh của tất cả các tiền tố của s.

Sample Input 1

a2A

Sample Output 1

1

Sample Input 1

abacaba

Sample Output 1

6

Giải thích :

chuỗi s = "abacaba" có 7 tiền tố

a -> 1_meh

ab -> 0_meh

aba -> 2_meh

abac -> 0_meh

abaca -> 0_meh

abacab -> 0_meh

abacaba -> 3_meh

1 + 0 + 2 + 0 + 0 + 0 + 3 = 6

Xoắn là một cậu bé rất thích những bài tập về chuỗi, cậu cảm thấy thoải mái khi loại bỏ những kí tự ở đầu chuỗi, hoặc cuối chuỗi, nhưng lại rất ghét khi phải loại bỏ các kí tự ở giữa chuỗi, tức là những kí tự không phải ở đầu hoặc cuối chuỗi.

Một hôm Trâu có cho cậu một chuỗi toàn kí tự 'D', 'H' và 'A', Trâu đố Xoắn tìm được chuỗi con ngắn nhất của chuỗi vừa cho, sao cho chuỗi con đó có ít nhất k kí tự 'D', k kí tự 'H' và k kí tự 'A . Xoắn thừa sức làm bài ez như vậy, xoắn thêm yêu cầu cho bản thân là chuỗi con đó có thể chuyển thành chuỗi có đúng k kí tự 'D', k kí tự 'H' và k kí tự 'A' bằng cách chỉ sử dụng ba loại thao tác xóa kí tự ở đầu/cuối/giữa chuỗi và số lần phải xóa kí tự ở giữa là ít nhất.

X là chuỗi con của Y là một chuỗi gồm các kí tự liên tiếp của Y

Input

Dòng đầu tiên chứa số k ~(1 \le k \le n/3) ~.

Dòng thứ 2 chuỗi s chỉ gồm các kí tự thuộc tập {'D', 'H', 'A'} có độ dài là n ~(1 \le n \le 2.10^5 )~

Output

In ra số lần phải xóa kí tự ở giữa, nếu k có chuỗi con nào thỏa mãn in ra -1.

Sample Input 1

2
DHHDHADHHAAAHD

Sample Output 1

1

Giải thích IN/OUTPUT 1 :

Chuỗi con Xoắn sẽ tìm được là "DHADHHA" chỉ phải loại thực hiện 1 thao tác xóa ở giữa là tại vị trí 2 thành chuỗi "DADHHA" có đúng 2 kí tự 'D', 2 kí tự 'H' và 2 kí tự 'A'

Nguồn đề: CLB GTLT FITHOU, mọi sự sao chép yêu cầu thêm đường dẫn tới bài tập, xin chân thành cảm ơn.

Tại một thành phố Z có một hệ thống điện có thể mô tả như một ma trận có n hàng và m cột. Mỗi một ô trong ma trận là một viên năng lượng tích điện, viên năng lượng có thể tích điện dương (1), tích điện âm(-1) , hoặc không tích điện(0).

Đạt là một kĩ sư điện tài năng mới du học về từ Nhật Bản, đạt thực hiện nối hai viên năng lượng tại hai ô (x1,y1) (x2,y2) với nhau, hai viên sau khi nối lại với nhau sẽ có cùng điện tích ban đầu nếu điện tích của hai viên giống nhau, nếu khác thì sẽ theo quy luật sau :

Gọi dt1 là điện tích của viên năng lượng tại ô (x1,y1), dt2 là điện tích của viên năng lượng tại ô (x2,y2), dt sẽ là điện tích của hai viên năng lượng sau khi Đạt nối chúng lại với nhau.

• dt1 = 1, dt2 = 0 => dt = 1
• dt1 = 0, dt2 = 1 => dt = 1
• dt1 = -1, dt2 = 0 => dt = -1
• dt1 = 0, dt2 = -1 => dt = -1
• dt1 = 1, dt2 = -1 => dt = 0
• dt1 = -1, dt2 = 1 => dt = 0

Ngoài ra sau khi nối hai viên năng lượng lại với nhau chúng sẽ được tính là một viên thống nhất, và luôn luôn có cùng điện tích với nhau, nếu điện tích của viên năng lượng thứ nhất thay đổi, điện tích viên năng lượng thứ hai cũng sẽ thay đổi theo và ngược lại

Thi thoảng, sau khi nối vài viên Đạt muốn kiểm tra điện tích hiện tại của một viên bất kì, hãy giúp Đạt kiểm tra.

Input

Dòng đầu tiên chứa hai số nguyên n, m - số dòng và cột của ma trận ~(1 \le n,m \le 10^3 )~

n dòng tiếp theo, mỗi dòng thứ i sẽ có m số nguyên, số nguyên thứ j cho biết điện tích ban đầu của viên năng lượng tại ô (i,j) (điện tích dương: 1, điện tích âm: -1, không có điện tích: 0)

Dòng tiếp theo chứa một số nguyên q số lượng thao tác của đạt,

q dòng tiếp theo mỗi dòng miêu tả một thao tác, có 2 loại thao tác : ~(1 \le q \le 10^5 )~

Thao tác loại 1 gồm 3 số nguyên:

• type, x, y với type = 1, đạt sẽ kiểm tra xem điện tích hiện tại của viên năng lượng tại ô (x,y) là gì.
• ~(1 \le x \le n )~ , ~(1 \le y \le m )~

Thao tác loại 2 gồm 5 số nguyên:

• type, x1, y1, x2, y2 với type = 2, đạt sẽ nối hai viên năng lượng (x1,y1) và (x2,y2) lại với nhau.
• ~(1 \le x1,x2 \le n )~ , ~(1 \le y1,y2 \le m )~

Output

Với mỗi thao tác loại 1 hãy in ra điện tích hiện tại của viên năng lượng tại (x,y) trên 1 dòng.

Sample Input 1

5 5
0 0 0 0 1
0 0 0 0 0
0 1 -1 0 0
0 0 0 0 0
1 0 0 0 -1
9
2 1 1 1 2
2 1 2 1 3
2 1 1 1 5
1 1 2
2 5 2 5 5
2 5 2 5 3
1 5 2
2 1 2 5 2
1 1 1

Sample Output 1

1
-1
0

20% điểm tương ứng với ~(1 \le n,m \le 50 )~, ~(1 \le q \le 100 )~

80% điểm tương ứng với ~(1 \le n,m \le 1000 )~, ~(1 \le q \le 10^5 )~

Nguồn đề: CLB GTLT FITHOU, mọi sự sao chép yêu cầu thêm đường dẫn tới bài tập, xin chân thành cảm ơn.

Có dãy 2, 6, 12, 20, 30, ..., n * (n + 1)

Hãy tính ~f(n)~ với ~f(n)~ bằng :

~ \sum_{i = 1}^{n} f(i*(i+1)) ~

Input

Dòng đầu tiên chứa một số nguyên t - số lượng test ~(1 \le t \le 10^5 )~

t dòng tiếp theo, mỗi dòng chứa 1 số nguyên n ~(1 \le n \le 10^{8} )~

Output

Với mỗi test in ra tổng của phần tử thứ nhất đến phần tử thứ n của dãy, kết quả chia dư với mod = ~ (10^9 + 7)~

Sample Input 1

5
1
2
3
4
100

Sample Output 1

2
8
20
40
343400

Giải thích : n = 2 , 1x(1+1) + 2x(2+1) = 1x2 + 2x3 = 8

10% điểm tương ứng với ~(1 \le t \le 10^3 )~ và ~(1 \le n \le 10^{2} )~

90% điểm tương ứng với ~(1 \le t \le 10^5 )~ và ~(1 \le n \le 10^{8} )~