RR và TA ngoài việc làm admin ở VNOI còn có nghề tay trái là người mẫu chụp ảnh trang bìa. Nghề này giúp đôi bạn không những nuôi sống được bản thân mà còn dành dụm được một số tiền kha khá. Vào một ngày đẹp trời, hai người quyết định đi tìm cho mình một tổ ấm. Các bạn đừng suy nghĩ lệch lạc, họ chỉ muốn mua hai ngồi nhà ở gần nhau để tiện bề đàm đạo với nhau về nhân tình thế thái, V-Pop, K-Pop và các thứ tương tự ...

RR và TA tìm mãi mới ra một khu phố rất đặc biệt mà hai người rất hài lòng. Ngoài NN ngồi nhà đẹp rạng ngời được đánh số từ 11 đến NN thì hệ thống đường xá của khu phố này cũng rất đáng chú ý. Tại đây, một số cặp ngôi nhà được nối với nhau bởi một con phố có độ dài một đơn vị. Điều này thì chẳng có gì lạ, nhưng đặc biệt là số lượng các con phố dù rất ít nhưng lại được thiết kế rất khoa học. Cụ thể là chỉ có N−1N−1 con phố nhưng cũng đủ để hai ngôi nhà bất kì đều đến được nhau. Mua nhà ở đây thì không sợ bị lạc mà chỉ đường cho bạn bè đến chơi cũng tiện, hạnh phúc là đây rồi! Thế là RR và TA hăm hở đi rút tiền mua nhà.

flashmt (vừa trúng vé số) cũng định mua nhà ở khu phố này. Nhưng buồn một nỗi, thầy phong thủy trứ danh technolt (cũng là nghề tay trái thôi) lại phán rằng flashmt và "đôi bạn hoàn hảo" RR - TA không hợp tuổi nên anh không nên ở gần hai người này, nếu không sự nghiệp cũng tiêu tan mà tình duyên cũng ngang trái. Nhưng vì là bạn thân của hai người, flashmt vẫn muốn mua nhà ở đây để tiện bề hú hí với nhau. Thầy phong thủy cảnh báo flashmt rằng độ an toàn của flashmt chính bằng khoảng cách từ nhà anh đến ngôi nhà gần nhất trong số hai ngôi nhà của RR và TA. Muốn được bình yên thì dĩ nhiên độ an toàn phải càng lớn càng tốt!

Biết được vị trí hai ngôi nhà của RR và TA, bạn hãy tính xem độ an toàn lớn nhất mà flashmt có thể đạt được là bao nhiêu!

Input

Dòng đầu ghi số nguyên dương TT - số bộ test (T≤5)(T≤5).

Tiếp theo là TT test, mỗi test gồm:

Dòng đầu tiên chứa số nguyên dương NN (1≤N≤50000)(1≤N≤50000) .

Tiếp theo là N−1N−1 dòng, mỗi dòng gồm 22 số nguyên dương u,vu,v cho biết có cạnh nối giữa đỉnh ngôi nhà uu và ngôi nhà vv.

Dòng tiếp theo chứa số nguyên dương QQ (1≤Q≤50000)(1≤Q≤50000).

QQ dòng tiếp theo, mỗi dòng gồm 22số nguyên dương u,vu,v mô tả vị trí hai ngôi nhà của RR và TA.

Các dấu cách và dòng trống thừa có thể xuất hiện ở bất kỳ vị trí nào trong file input.

Output

Output của mỗi bộ test gồm QQ dòng. Mỗi dòng in ra một số nguyên dương duy nhất là đáp án của truy vấn tương ứng.

Giới hạn

Trong 30%30% số test, 1≤N,Q≤1001≤N,Q≤100.

input:

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

output:

2
3
3
3
3
2
3

Các học sinh khi đến thực tập trong phòng máy tính thường hay chơi trò chơi điện tử trên mạng. Để ngăn ngừa, người trực phòng máy đã ngắt tất cả các máy tính ra khỏi mạng và xếp chúng thành một dãy trên một cái bàn dài và gắn chặt máy xuống mặt bàn rồi đánh số thứ tự các máy từ 11 đến NN theo chiều từ trái sang phải. Các học sinh tinh nghịch không chịu thua, họ đã quyết định tìm cách nối các máy trên bàn bởi các đoạn dây nối sao cho mỗi máy được nối với ít nhất một máy khác. Để tiến hành công việc này, họ đã đo khoảng cách giữa hai máy liên tiếp. Bạn hãy giúp các học sinh này tìm cách nối mạng thoả mãn yêu cầu đặt ra sao cho tổng độ dài cáp nối phải sử dụng là ít nhất.

Input

Dòng đầu tiên chứa số lượng máy NN (1≤N≤25000)(1≤N≤25000).

Dòng thứ ii trong số N−1N−1 dòng tiếp theo chứa các khoảng cách từ máy ii đến máy i+1i+1 (i=1(i=1, 22, ..., N−1)N−1). Giả thiết rằng khoảng cách từ máy 11 đến máy NN không vượt quá 106106.

Output

Ghi ra độ dài của cáp nối cần sử dụng.

Sample Input

6
2
2
3
2
2

output:

7

Như vậy là chỉ còn một tuần nữa, quả bóng Tango 12 sẽ bắt đầu lăn trên các sân cỏ Poland và Ukraine, 2 quốc gia đăng cai tổ chức EURO 2012 - ngày hội bóng đá được mong chờ nhất trong năm nay. Trong bầu không khí đang nóng dần lên từng ngày này, EURO 2012 đã được rất nhiều doanh nghiệp chọn làm chủ đề cho các chương trình khuyến mãi hay sự kiện với mục đích thu hút sự quan tâm từ lực lượng đông đảo fan hâm mộ môn thể thao vua. Do đó, các nhà tổ chức kì thi Virtual Marathon 2012 (VM12) quyết định treo giải thưởng một cặp vé xem trận chung kết dành cho đội vô địch kì thi này. Đội của Raldono và Balitello, hai nhân vật chính của chúng ta hôm nay, dù đã cố gắng hết sức nhưng đành dừng bước ở vị trí thứ 7, nhận được giải khuyến khích cùng một phần quà từ ban tổ chức.

Phần quà là TT tấm poster hình chữ nhật, mỗi tấm được chia ra thành M×NM×N ô vuông nhỏ (kích thước M,NM,N cho các tấm poster có thể khác nhau). Trong đó, mỗi ô là một tấm thẻ sưu tập hình các cầu thủ nổi tiếng. Raldono quyết định chia các tấm thẻ cho hai người theo cách sau. Ban đầu mỗi người sẽ chọn tất cả tấm thẻ có hình cầu thủ mình yêu thích, sau đó những tấm thẻ còn lại trên poster sẽ được chia ngẫu nhiên. Balitello lại muốn sau khi chia xong các tấm thẻ, nếu cắt ra 1 hình vuông bất kì (có các cạnh song song với cạnh của poster) từ tấm poster thì chênh lệch số thẻ được chia cho mỗi người trong hình vuông đó không vượt quá 22.

Ví dụ trong hình trên, những tấm thẻ Raldono chọn là ô màu vàng, Balitello chọn là ô màu xanh thì 2 cách chia đầu là hợp lệ, 2 cách chia sau là không hợp lệ (những hình vuông được viền đỏ không thỏa yêu cầu).

Với mỗi tấm poster, cho biết những tấm thẻ có hình cầu thủ yêu thích của mỗi người, hãy giúp Raldono và Balitello đếm xem có tất cả bao nhiêu cách chia các tấm thẻ trên tấm poster đó thỏa yêu cầu của cả hai đặt ra.

Input

Dòng 1 ghi số TT, số tấm poster (1≤T≤1000)(1≤T≤1000).

Tiếp theo là TT bộ test, mỗi bộ được mô tả như sau:

Dòng đầu ghi số MM và NN (1≤M,N≤5)(1≤M,N≤5).

Dòng thứ ii trong MM dòng tiếp theo gồm NN kí tự, kí tự thứ jj mô tả tấm thẻ ở hàng ii cột jj của tấm poster ('R' nếu chứa hình cầu thủ Raldono yêu thích, 'B' nếu chứa hình cầu thủ Balitello yêu thích, '.' là những tấm thẻ sẽ được chia ngẫu nhiên).

Output

Xuất ra TT dòng, mỗi dòng chứa kết quả là số cách chia cho tấm poster tương ứng.

Sample Input

input:

5 2 2 BR RB 4 4 ..RR .BRR .BB. .... 2 3 ... BBR 3 3 BBB BR. ... 3 3 ... .R. ...

output:

1 0 6 3 102

Max - Min của đoạn:

algorit là một nhà toán học đại tài, người có chỉ số iq cao nhất nhân loại nếu đếm ngược. Đặc biệt anh rất thích thú với những thứ to và nhỏ, các con số không phải là ngoại lệ. Bởi vậy hôm nay algorit đang thắc mắc một bài toán như sau :

Bạn được cung cấp một dãy số gồm nn số nguyên A1,A2,...,AnA1,A2,...,An.

Nhiệm vụ của bạn là đếm số lượng đoạn con có max−min=kmax−min=k. Ở đây maxmax và minmin là giá trị lớn nhất và giá trị nhỏ nhất của đoạn con đó.

algorit suy nghĩ bài toán này đến mức hói cả đầu mà vẫn chưa nghĩ ra, các bạn hãy giúp algorit nhé !

Input

Dòng đầu tiên gồm 2 số nguyên n,k(0≤k≤109)n,k(0≤k≤109).

Dòng thứ 2 gồm nn số nguyên A1,A2,A3,...,An(−109≤Ai≤109)A1,A2,A3,...,An(−109≤Ai≤109).

Output

Gồm một số nguyên duy nhất là số lượng đoạn con thỏa mãn.

SampleInput:

input: 

5 2
1 2 1 3 3

output:

6

Ràng buộc :

40% số điểm tương ứng với : n≤103n≤103.

30% số điểm tương ứng với : n≤105n≤105.

30% số điểm tương ứng với : n≤5∗105n≤5∗105.

Minigame ôn luyện cho những bạn vào vòng 2 gồm 2 bài (do Nguyễn Lê Phước Thịnh tài trợ)

những bạn làm được hết 2 bài sẽ được thưởng 5 gp còn các bạn làm được 1 bài 2 gb :

bài 1: Nobita và cuộc chiến giữa các hành tinh:

Nobita là 1 đứa trẻ vô cùng hậu đậu, vụng về, đôi lúc khá đãng trí nhưng cậu lại có khả năng bắn súng vô cùng thiện xạ. Vào 1 ngày đẹp trời, Doraemon rủ cậu chơi 1 trò chơi đến từ tương lai. Trò chơi đưa Nobita đến 1 thế giới nơi đó cậu ta có thể trở thành 1 siêu anh hùng cứu thế giới khỏi sự xâm lược của người ngoài hành tinh. Trò chơi có 101 màn, nhưng với tài năng xuất chúng của mình nobita đã vuợt 100 màn đầu tiên 1 cách rất dễ dàng. Nhưng đến màn cuối cùng, xung quanh bỗng nhiên xuất hiện rất nhiều UFO của kẻ thù. Bởi vì đây là màn cuối nên rất khó, các UFO có thể phân thân để gây nhiễu loạn cho nobita. Nếu có vô số đạn nobita sẽ dễ dàng vượt qua trò chơi này. Nhưng trò chơi chỉ cho Nobita 1 số lượng đạn nhất định tương ứng với số lượng các UFO cần tiêu diệt (Nếu bắn lung tung thì Nobia có thể mất đạn lãng phí, không tiêu diệt được hết kẻ thù và thua cuộc). Vì vậy Nobita cần phải bắn chính xác ko được trượt phát nào. Ngoài ra, các UFO còn có thể thay đổi độ cao theo thời gian. Trò chơi biết rằng dù Nobita rất giỏi bắn súng nhưng lại chưa dủ trình độ để nhận biết đâu là UFO chính, đâu là bản sao. Nên trò chơi phải cho Nobita một vài gợi ý để cậu ta có khả năng chiến thắng cao hơn. Ban đầu, trò chơi sẽ cung cấp vị trí, độ cao ban đầu của các UFO (cả chính, lẫn bản sao). Một lần, trò chơi sẽ cung cấp cho Nobita 1 thông tin của kẻ thù:

1 u v: là UFO uu thay đổi độ cao thành vv.

2 u v val: UFO cần tiêu diệt chính sẽ nằm ở vị trí nằm trong khoảng từ uu đến vv, gần bên trái nhất và đang bay ở độ cao thấp hơn hoặc bằng valval.

Tuy đã đưa ra nhưng gợi ý rất chi tiết như vậy nhưng Nobita vẫn chưa thể giải được gợi ý và nhận biết được đâu ra UFO của kẻ thù. Chính vì vậy cậu mới nhờ đến các lập trình viên tương lai. Với tài năng xuất chúng của các lập trình viên trên LQDOJ, các bạn hãy dùng trí thông minh của mình để giúp Nobita nhé. Nobita xin cảm ơn các bạn bằng 1 nghìn lời cảm ơn!!!!!!!!!!!

Input:

Dòng đầu chứa hai số nguyên n,qn,q - là số lượng UFO ban đầu, số lượng gợi ý. (1≤n≤105,1≤q≤106)(1≤n≤105,1≤q≤106)

Dòng tiếp theo gồm a1,a2,a3,...,ana1,a2,a3,...,an là độ cao ban đầu của các UFO. (0≤ai≤109)(0≤ai≤109)

qq dòng tiếp theo - là nội dung các gợi ý cần giải quyết:

1 u v (1≤u≤n,0≤v≤109)(1≤u≤n,0≤v≤109)

2 u v val (1≤u≤v≤n,0≤val≤109)(1≤u≤v≤n,0≤val≤109)

Output:

Với mỗi gợi ý 2 cần trả lời vị trí UFO Nobita cần tiêu diệt:

Nếu có vị trí tồn tại, in ra vị trí đó.

Nếu không, in ra "Skip" để Nobita bỏ qua, ko bắn.

Test ví dụ:

Input:

output:

bài 2: K-Amazing Numbers

Cho mảng aa gồm nn số nguyên dương

Gọi qkqk là số nguyên nhỏ nhất có mặt ở tất cả các đoạn con (gồm các phần tử liên tiếp) có kích thước là kk.

Nếu không tồn tại qkqk thỏa mãn điều trên thì qk=−1qk=−1.

Nhiệm vụ của chúng ta là in ra tất cả các giá trị qiqi với 1≤i≤n1≤i≤n.

Input:

Dòng thứ nhất chứa số nguyên t(1≤t≤1000)t(1≤t≤1000) - Thể hiện số lượng testcase

Tiếp theo là tt block, mỗi block có dạng như sau:

Dòng thứ nhất chứa số nguyên n(1≤n≤3.105)n(1≤n≤3.105)

Dòng thứ hai chứa số nguyên a1,a2,...,ana1,a2,...,an với 1≤ai≤n1≤ai≤n

(Biết rằng: Tổng các giá trị của nn ở tất cả testcase không quá 3.1053.105)

Output:

ứng với mỗi testcase ,in ra các giá trị q1,q2,...,qnq1,q2,...,qn tương ứng

Ví dụ:

Input:

output