Sorry Contest (Div 1)

Vì đang trong thời gian cách ly xã hội, CaiWinDao không thể đến nhà các em gái chơi. Anh đành ở nhà chơi với một người bạn mới là con Bot do chính mình sáng chế. Mỗi ngày, con Bot sẽ gợi ý CaiWinDao một trò chơi và hai "người" sẽ chơi với nhau xem ai thắng. Hôm nay, con Bot đưa cho CaiWinDao \(n\) que diêm. Nhiệm vụ của anh là phải tạo thành một hình chữ nhật rỗng bằng các que diêm đã cho sao cho diện tích hình chữ nhật tạo được là lớn nhất có thể. Lưu ý rằng, CaiWinDao không cần xài hết \(n\) que diêm.

Input

• Gồm một dòng chứa số que diêm, \(n \ (n > 0)\).

Output

• Gồm một số nguyên là diện tích lớn nhất có thể tạo thành.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 1000\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \leq 10^5\).
• Subtask \(3\) (\(30\%\) số điểm): \(n \leq 10^9\).

Example

4

1

17

16

3

0

ami không thích ước chung lớn nhất. Do đó, ami sẽ cần các bạn tìm ước chung lớn nhất giúp ami. Cho một dãy \(n\) số nguyên dương. Hãy tính ước chung lớn nhất của \(n\) số này.

"Dễ quá" - các bạn thầm nghĩ. Vậy nên ami muốn các bạn bỏ đi đúng 1 số để ước chung lớn nhất của các số còn lại là lớn nhất.

"Vẫn quá dễ" - các bạn cười thầm. Vì thế, hãy bỏ đi \(k\) số để ước chung lớn nhất của các số còn lại là lớn nhất nhé.

Input

• Dòng đầu chứa 2 số nguyên \(n\) và \(k\).

• Dòng tiếp theo chứa n số nguyên dương \(a_1\), \(a_2\), ..., \(a_n \ (1 \leq a_i \leq 3 \times 10^6)\).

Output

• In ra \(1\) dòng là ước chung lớn nhất của dãy số sau khi đã bỏ đi đúng k số.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(1 \leq n \leq 10\), và \(k = 0\).

• Subtask \(2\) (\(30\%\) số điểm): \(1 \leq n \leq 10^5\), và \(k = 1\).

• Subtask \(3\) (\(30\%\) số điểm): \(0 \leq k < n \leq 3*10^5\), và \(1 \leq a_i \leq 10^5\).

• Subtask \(4\) (\(30\%\) số điểm): \(0 \leq k < n \leq 3*10^5\), và \(1 \leq a_i \leq 3*10^6\).

Example

3 1
1 2 2 

2

Hàm \(F(a)\) với a là một dãy số nguyên \(n \geq 1\) phần tử \(a_1\), \(a_2\), \(a_3\), ... \(a_n\) được định nghĩa thông qua đoạn code sau :

    F(a) = 0;
    Duyệt i từ 2 đến n
    {
       k = 0;
       Duyệt e từ 1 đến i-1
       {
           Nếu a[e] < a[i] thì
           {
               k = k + 1;
           }
       }
       F(a) = F(a) + k * a[i];
    }

cuom1999 thích những thứ nhỏ bé (ví dụ như Small), do đó cuom1999 muốn ami tính hàm F với tất cả các dãy số tự nhiên có độ dài bằng 2. Quá dễ, đáp án luôn là +∞. Còn ami thích những ghứ vĩ đại, do đó ami muốn các bạn tính tổng tất cả các hàm F(a) với a là một hoán vị n phần tử. Vì kết quả có thể lớn, các bạn cần in ra đáp số chia dư 1000000007.

Input

• Dòng đầu tiên chứa 1 số nguyên dương \(q\) là số câu hỏi.
• \(q\) tiếp theo, mỗi dòng dòng chứa 1 số nguyên dương \(n\).

Output

• In ra \(q\) dòng, mỗi dòng ứng với một câu hỏi.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(1 \leq n \leq 10\), \(q\) = 1.

• Subtask \(2\) (\(30\%\) số điểm): \(1 \leq n \leq 100\), \(q\) = 1.

• Subtask \(3\) (\(60\%\) số điểm): \(1 \leq n \leq 10^6\), \(1 \leq q \leq 10^6\).

Example

4
1
2
3
4

0
2
24
240

Có \(n\) con kiến trên một sợi dây. Chúng được đánh số thứ tự từ \(1\) đến \(n\). Quy ước tọa độ của sợi dây là một trục \(Ox\) với hai đầu mút là \(-10^9\) và \(10^9\). Ban đầu các con kiến đứng tại tọa độ \(a_1, a_2, ..., a_n\). Mỗi giây, mỗi con kiến có thể bò sang trái \(1\) đơn vị, sang phải \(1\) đơn vị, hoặc đứng yên. Nói cách khác, sau mỗi giây, \(a_i=a_i + 1, a_i - 1\) hoặc \(a_i\).

Kiến Vua rất không hài lòng vì thứ tự các con kiến đứng rất lộn xộn, vì vậy ông muốn chúng di chuyển về lại trật tự để dễ quản lý. Ông muốn con kiến thứ nhất đứng bên trái con thứ hai, con thứ hai đứng bên trái con thứ ba, ... Hay nói cách khác, \(a_1 < a_2 < ... < a_n\).

Hỏi cần ít nhất bao nhiêu giây để các con kiến tạo thành trật tự như nhà vua mong muốn nếu chúng di chuyển một cách tối ưu? Biết rằng nhà vua chỉ kiểm tra trật tự tại các thời điểm là số nguyên. Giả sử sợi dây đủ rộng để các con kiến không bị rơi xuống đất khi gặp nhau.

Input

• Dòng đầu chứ một số nguyên dương \(n\) là số lượng kiến trên dây.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, ..., a_n \ (-10^8 \leq a_i \leq 10^8)\) là tọa độ ban đầu của các con kiến.

Output

• Dòng đầu in ra một số nguyên dương là thời gian ít nhất để các con kiến di chuyển và tạo thành trật tự nhà vua mong muốn.

• Dòng thứ hai in ra \(n\) số nguyên \(b_1, b_2, ..., b_n \ (-10^9 \leq b_i \leq 10^9)\) là tọa độ của các con kiến sau khi di chuyển xong.

• Lưu ý:

• Nếu in đúng đáp án dòng 1, bạn sẽ được \(50\%\) số điểm của test tương ứng.
• Nếu có nhiều phương án cho dòng 2, bạn chỉ cần in một đáp án bất kỳ

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(n \leq 3000\).
• Subtask \(2\) (\(60\%\) số điểm): \(n \leq 3 \times 10^5\).

Example

3
3 2 1

2
1 2 3

4
1 2 3 4

0
1 2 3 4

Gieo xúc xắc là cách giết thời gian duy nhất của CaiWinDao trong thời kỳ giãn cách xã hội này. Dù con xúc xắc ngà voi của CaiWinDao được chế tác rất đẹp mắt nhưng rồi gieo mãi cũng thành nhàm, cậu bắt đầu lấy số điểm thu được từ các lần gieo nhân lại với nhau. Một ý tưởng chợt nảy ra trong đầu CaiWinDao, cậu thách đố cuom1999 đếm được số cách gieo con xúc xắc này đúng \(n\) lần sao cho tích số điểm của \(n\) lần gieo đó đúng bằng một số nguyên dương \(m\). Vì số cách rất lớn nên CaiWinDao cho phép cuom1999 chỉ cần trả lời kết quả thu được sau khi lấy đáp số đó chia lấy phần dư cho \(10^9+7\).

Buồn thay, cuom1999 đang tất bật chuẩn bị cho học kỳ mới nên không có thời gian để nghiền ngẫm câu đố vu vơ của CaiWinDao. Các bạn hãy góp sức giúp đỡ cậu ấy nhé!

Lưu ý rằng:

• Hai cách gieo được tính là khác nhau nếu tồn tại một lượt gieo cho số điểm khác nhau ở hai cách.
• Sáu mặt của con xúc xắc ngà tương ứng với sáu điểm số khác nhau \(1\), \(2\), \(3\), \(4\), \(5\) và \(6\).

Input

• Gồm một dòng duy nhất chứa hai số nguyên dương \(n\) và \(m\).

Output

• Chứa một số nguyên duy nhất là số cách tìm được chia lấy phần dư cho \(10^9+7\).

Scoring

• Subtask #1 (\(20\%\) số điểm): \(n\leq 9, m\leq 50000\).
• Subtask #2 (\(20\%\) số điểm): \(n\leq 100, m\leq 50000\).
• Subtask #3 (\(60\%\) số điểm): \(n\leq 100, m\leq 10^{18}\).

Example

2 12

4

8 450

2520

cuom1999 đang đánh Liên Minh Huyền Thoại với vị tướng tủ soilehpa. cuom1999 đã đánh từng trận một. Mỗi trận có một hệ số phong độ là \(a_i\). Nếu phong độ gánh team của ami không nhỏ hơn \(a_i\), cuom1999 sẽ chiến thắng ván đấu đó. Cứ mỗi một ván thắng, phong độ của ami lại tăng lên đúng \(a_i\). Hiện tại, có \(n\) trận đấu, với các chỉ số phong độ lần lượt là \(a_1\), \(a_2\), ..., \(a_n\), cuom1999 muốn cho ami tập tạ, nên sẽ có \(q\) truy vấn, mỗi truy vấn thuộc 2 loại sau :

1. cuom1999 thay đổi hệ số phong độ của trận đấu \(i\) thành \(x\)

2. cuom1999 hỏi xem nếu ami lần lượt đánh các trận từ \(l\) đến \(r\) thì cần phong độ ban đầu tối thiểu (trước khi đánh) là bao nhiêu để chắc chắn thắng tất cả các trận đấu đó.

Ví dụ : Nếu ami cần thắng các trận có chỉ số phong độ lần lượt là \(1, 2, 3\) thì ami cần ít nhất 1 điểm phong độ trước khi đánh. Sau trận đầu tiên, ami sẽ có phong độ là \(1 + 1 = 2\), đủ để thắng trận 2. Sau trận thứ hai, ami sẽ có phong độ là \(2 + 2 = 4\), và dễ dàng chiến thắng trận 3.

Vì ami đang bận gánh team, các bạn sẽ thay ami trả lời câu hỏi này.

Input

• Dòng đầu chứa 2 số nguyên dương \(n\) và \(q\).

• Dòng tiếp theo chứ n số nguyên dương \(a_1\), \(a_2\), ..., \(a_n\) là chỉ số phong độ của ván đấu.

• q dòng cuối cùng có dạng sau:

• 1 i x : cuom1999 thay \(a_i\) = \(x\) \((0 \leq x \leq 10^9,\) \(1 \leq i \leq n)\)

• 2 l r : cuom1999 muốn hỏi xem ami cần ít nhất bao nhiêu điểm phong độ để lần lượt thắng các trận đấu \(a_l\), \(a_{l+1}\), ..., \(a_r\) \((1 \leq l \leq r \leq n)\).

Output

• Với mỗi truy vấn 2, in ra kết quả.

• Dữ liệu đảm bảo luôn có ít nhất một truy vấn loại 2.

Scoring

• Trong tất cả các test, \(1 \leq x, a_i \leq 10^9\) , \(1 \leq i \leq n\).
• Subtask \(1\) (\(20\%\) số điểm): \(2 \leq n , q \leq 1000\).
• Subtask \(2\) (\(40\%\) số điểm): \(2 \leq n , q \leq 100000\), và không có truy vấn loại 1.
• Subtask \(3\) (\(40\%\) số điểm): \(2 \leq n , q \leq 300000\).

Example

3 3
1 2 3
2 1 2
1 1 3
2 1 3 

1
3

10 10
1 2 3 4 5 6 7 8 9 10
2 1 2
1 1 3
2 1 3
1 5 20
1 6 1000
2 1 7
2 1 5
2 1 10
1 3 69
2 2 7 

1
3
968
8
968
905