### Update: [Tutorial of SoTL gen 6 programming team Entrance test](/mKPX-sqGT4efZxnhKlFqxw)

**Thông báo:** Đơn tuyển thành viên đã được kéo đến ngày 15/9. Vì đã có nhiều người giải được full 4 bài rồi nên sẽ có bài thứ 5 các bạn nhé. Bài thứ 5 sẽ được cập nhật ngày 9/9.

**Lưu ý:** không giới hạn số lượt nộp bài.
**Vui lòng đọc thật kĩ phần *Hướng dẫn nộp bài* cũng như phần `Questions about problems` trên Codeforces trước khi làm để tránh lỗi không đáng có.**

:::spoiler Hướng dẫn nộp bài
:::info

Sau khi truy cập [link nộp bài](https://codeforces.com/contestInvitation/cc4a71548ef5c58cd5b3761f49ed7ddc38f13b6d) và **Register** xong, hãy truy cập lại link nộp bài rồi click **Enter**

Để gửi lời giải của bạn, click **SUBMIT CODE**

Tiếp theo, chọn bài và ngôn ngữ:
- **Pascal**: nên chọn **Free Pascal 3.0.2**
- **Python**: nên chọn **Python 3.8.10**
- Bạn có thể sẽ bị Time limit exceeded nếu chọn **PyPy**. Lí do: hàm `input()` trong PyPy nặng hơn nhiều so với hàm `input()` trong Python, nên nó sẽ chạy khá lâu đối với những testcase lớn.
- Nếu bạn vẫn muốn chọn **PyPy** (vì một lí do nào đó), hãy thêm 2 dòng sau vào đầu đoạn code để tăng tốc độ đọc input:

    import sys
    input = sys.stdin.readline

- **C++**: nên chọn **GNU G++20 11.2.0 (64 bit, winlibs)** (không chọn **Clang++** và **MSVC++**)
- **Java**: nên chọn **Java 17 64bit**

Bạn không nhất thiết phải biết lập trình để được tuyển vào SoTL. Như đã đề cập ở phần đầu, hãy thoải mái nếu bạn không biết ngôn ngữ lập trình nào và gửi cách làm của bạn dưới ngôn ngữ **Haskell**. Đừng hoang mang nếu bạn nhận được Compilation error, mình vẫn sẽ đọc lời giải của bạn.

Ví dụ, đề bài là: Cho một mảng số nguyên, hãy tìm số lớn nhất của mảng đó.
Bạn có thể gửi lời giải dưới ngôn ngữ **Haskell** như sau:

Đầu tiên, sắp xếp lại mảng theo thứ tự không giảm dần, sau đó in ra phần tử cuối cùng của mảng.

Nếu bạn có thắc mắc về đề bài, đừng ngần ngại hỏi ở phần này 

Dưới đây là ~~4~~ 5 bài tập để bạn thử sức, chúc bạn may mắn, SoTL đang chờ bạn 🫡
:::

Độ khó của các bài không theo thứ tự từ trên xuống dưới, bạn nên đọc qua tất cả các bài

[Link nộp bài](https://codeforces.com/contestInvitation/cc4a71548ef5c58cd5b3761f49ed7ddc38f13b6d) (Bạn hãy đăng nhập [Codeforces](https://codeforces.com/enter) trước)

Chỉ cho phép ~~3~~ 4 ngôn ngữ lập trình: **Pascal**, **Python**, **C++** và **Java**. Nếu bạn không biết code mà chỉ có thể đưa ra hướng giải, hãy ghi hướng giải của bạn và nộp dưới ngôn ngữ **Haskell** (chắc chắn sẽ dẫn tới lỗi Compilation error, nhưng không sao, mình vẫn sẽ đọc câu trả lời của bạn).

| Bài | Tên bài | Giới hạn thời gian - bộ nhớ |
|:---:|:--------------------------------------------------------------------------------- | --------------------------- |
| A | [brownfox the First-grader](#A---brownfox-the-First-grader) | 1.0s - 256MB |
| B | [brownfox and Arrays](#B---brownfox-and-Arrays) | 2.0s - 256MB |
| C | [brownfox and Geometry](#C---brownfox-and-Geometry) | 2.0s - 256MB |
| D | [brownfox and Algebra](#D---brownfox-and-Algebra) | 1.0s - 256MB |
| E | [brownfox and Sum of Product of Pairs](#E---brownfox-and-Sum-of-Product-of-Pairs) | 3.0s - 256MB |
| F | ~~brownfox and Sum of Product of Triplets~~ | |

---

# A - brownfox the First-grader
> *Mọi thứ xung quanh bạn đều là toán học* **---** Shakuntala Devi

Sau một thời gian dài nghỉ hè, giờ đây, Fox chính thức là học sinh lớp một. Để chuẩn bị cho năm học mới, bố mẹ cho Fox tiền để mua đồ dùng học tập. Tuy nhiên, vì Fox chưa được học toán nên chưa biết tính tổng số tiền mà Fox phải trả cho $n$ món hàng. Bạn có thể tính giúp Fox không?

## Input
- Dòng đầu tiên chứa số nguyên dương $n$ ($1 \le n \le 10$),
- Dòng thứ hai chứa $n$ số nguyên dương: giá tiền của từng món hàng mà Fox mua.

Cho biết giá tiền của từng mặt hàng không vượt quá $50000$.

## Output
Một dòng duy nhất chứa số nguyên dương $S$ - tổng số tiền mà Fox phải trả cho tất cả $n$ món hàng.

## Test mẫu
### Input

4
3000 1000 5000 6000

### Output

15000

# B - brownfox and Arrays
> *Nên có một, và thà chỉ có một cách rõ ràng để làm điều đó* **---** The Zen of Python

*Đề bài giả sử chỉ số mảng được bắt đầu từ $0$.*

Fox rất thích những mảng số nguyên, vậy nên, vào một ngày đẹp trời SoTL đã cho Fox hai mảng $a$ với kích thước $n$ và $b$ với kích thước $m$ và yêu cầu Fox phải thực hiện $m$ thao tác như sau:

- Thao tác thứ $i$ ($0 \le i < m$), sắp xếp lại $b_i$ phần tử **cuối cùng** của $a$ theo thứ tự **không giảm dần**. Nói cách khác, sắp xếp lại $a_{n-b_i}$, $a_{n-b_i+1}$,.., $a_{n-1}$ sao cho $a_{n-b_i} \le a_{n-b_i+1} \le \ldots \le a_{n-1}$ (xem phần [Giải thích test mẫu](#Giải-thích-test-mẫu1) để hiểu rõ hơn).

Sau đó, vì SoTL được thành lập năm 2017 😊 nên Fox tạo một mảng $c$: $c_i = a_i \bmod 2017$ ($0 \le i < n$), $x \bmod y$ là phần dư của $x$ khi chia cho $y$.

Bạn hãy in ra mảng $c$.

## Input
- Dòng đầu tiên chứa hai số nguyên dương $n \le 5\cdot10^5$ và $m \le 5\cdot10^5$,
- Dòng thứ hai chứa $n$ số nguyên dương là mảng $a$ ($1 \le a_i \le 10^9$),
- Dòng thứ ba chứa $m$ số nguyên dương là mảng $b$ ($1 \le b_i \le n$).

## Output
$n$ số nguyên dương của mảng $c$.

Bạn có thể xuất các số trên một dòng hoặc xuất mỗi số một dòng.

## Test mẫu

### Input

5 2
229 142 2023 999999 2017
2 3

### Output

229 142 0 6 1584

### Giải thích test mẫu
Ban đầu, $a=[229,\space 142,\space 2023,\space 999999,\space 2017]$
- Sắp xếp lại $b_0=2$ phần tử cuối cùng của $a$, ta được $a=[229,\space 142,\space 2023,\space \textbf{2017, 999999}]$
- Sắp xếp lại $b_1=3$ phần tử cuối cùng của $a$, ta được $a=[229,\space 142,\space \textbf{2017, 2023, 999999}]$

Sau đó, ta tạo mảng $c$, $c=[229,\space 142,\space 0,\space 6,\space 1584]$

# C - brownfox and Geometry
> *Ở đâu có vật chất, ở đó có hình học* **---** Johannes Kepler

Fox có $n$ điểm trên hệ trục toạ độ $Oxy$: $(x_1, y_1),...(x_n, y_n)$. Bạn cần vẽ một **tam giác cân** $OAB$, $A \in Ox$, $B \in Oy$ sao cho **tất cả** $n$ điểm đều nằm trên hoặc trong tam giác này. Trong cách vẽ tam giác $OAB$ có diện tích nhỏ nhất, hãy in ra chiều dài 3 cạnh của tam giác này.

## Input
- Dòng đầu tiên: số nguyên dương $n$ ($1 \le n \le 5\cdot 10^5$),
- Dòng thứ $i$ trong $n$ dòng tiếp theo chứa hai số nguyên không âm $x_i$, $y_i$ ($0 \le x_i,\space y_i \le 10^9$) - toạ độ của điểm thứ $i$.

Điều kiện thêm: Luôn có ít nhất một điểm không trùng $O$. Nói cách khác, $\exists i \in [1, n]: x_i + y_i \neq 0$.

## Output
Chiều dài 3 cạnh của tam giác cân $OAB$ có diện tích nhỏ nhất (theo thứ tự không giảm dần). Đáp án của bạn sẽ được xem là chính xác nếu độ chênh lệch với đáp án chuẩn không vượt quá $10^{-4}$. Nói cách khác, giả sử đáp án của bạn là $a$, đáp án chuẩn là $b$, đáp án của bạn sẽ được chấp nhận nếu $|a-b| \le 10^{-4}$.

Bạn có thể xuất các số trên một dòng hoặc xuất mỗi số một dòng.

## Test mẫu

### Input

4
1 1
1 2
2 1
2 2

### Output

4.00000 4.00000 5.65685

### Giải thích test mẫu
Chiều dài các cạnh của tam giác cân $OAB$ này lần lượt là:
- $OA$: $4$
- $OB$: $4$
- $AB$: $5.65685$

Dễ thấy ta không thể vẽ tam giác cân $OAB$ có diện tích nhỏ hơn mà vẫn có thể chứa cả 4 điểm.

# D - brownfox and Algebra
> *Ở đâu có những con số, ở đó có cái đẹp* **---** Proclus Diadochus

Fox rất thích toán, nhưng vài ngày trước SoTL cho Fox một bài toán hóc búa mà Fox chưa thể giải được: Đếm xem từ $1$ tới $n$ có bao nhiêu số nguyên không chia hết cho bất kì số nguyên nào từ $2$ tới $10$. Fox rất sốt ruột vì mãi chưa thể giải được nên nhờ bạn giúp. Vì $2017$ là một số rất đặc biệt, nó là một số nguyên tố, đồng thời cũng là năm mà SoTL được thành lập, vậy nên bạn hãy in ra kết quả sau khi chia lấy dư cho $2017$ nhé!

## Input
Một số nguyên dương $n$.

**Phân bố điểm:**
- Subtask 1 (25 điểm): $1 \le n \le 10^3$
- Subtask 2 (25 điểm): $10^3 < n \le 10^6$
- Subtask 3 (25 điểm): $10^6 < n \le 10^9$
- Subtask 4 (25 điểm): $10^9 < n \le 10^{18}$

## Output
Kết quả của bài toán - số lượng số nguyên dương không lớn hơn $n$ mà không chia hết cho $x$, $\forall x \in [2; 10]$, sau khi chia lấy dư cho $2017$.

## Test mẫu

### Input

14

### Output

3

### Giải thích test mẫu
Từ $1$ tới $14$ có $3$ số không chia hết cho số nguyên nào từ $2$ tới $10$ là $1$, $11$ và $13$.

Một vài số nguyên đầu tiên không chia hết cho số nguyên nào từ $2$ tới $10$ là $1$, $11$, $13$, $17$, $19$, $23$, $29$, $31$, $37$, $41$, $43$, $47$, $53$, $59$, $61$, $67$, $71$, $73$, $79$, $83$, $89$, $97$, $101$, $103$, $107$, $109$, $113$, $121$, $127$, $131$, $137$, $139$, $143$, ...

# E - brownfox and Sum of Product of Pairs

*Đề bài giả sử chỉ số mảng được bắt đầu từ $1$*.

Cho một mảng gồm $n$ số nguyên dương $a_1$, $a_2$,.., $a_n$. Bạn hãy giúp Fox tính tổng của tất cả $a_i \cdot a_j$, với mọi cặp số $(i, j)$ thoả mãn $1 \le i < j \le n$ nhé.

Nói cách khác, hãy tính giá trị của:

$\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}(a_i \cdot a_j)$
$= a_1 \cdot a_2 + a_1 \cdot a_3 + a_1 \cdot a_4 + \ldots + a_1 \cdot a_n$
$+\space a_2 \cdot a_3 + a_2 \cdot a_4 + \ldots + a_2 \cdot a_n$
$+\space \ldots$
$+\space a_{n-2} \cdot a_{n-1} + a_{n-2} \cdot a_n$
$+\space a_{n-1} \cdot a_n$

## Input
**Đây là bài multi-test (có nhiều test case trong một test)**

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

$2\cdot t$ dòng tiếp theo - dữ liệu của $t$ test case:
- Dòng thứ nhất của mỗi test case chứa số nguyên $n$ - số lượng phần tử của mảng $a$.
- Dòng thứ hai của mỗi test case chứa $n$ số nguyên $a_1$, $a_2$,.., $a_n$ $(1\le a_i\le 10^4, \forall i \in [1, n])$ - các phần tử của mảng $a$.

**Phân bố điểm:**
Bạn phải đúng toàn bộ test trong một subtask để ăn điểm của subtask đó.
- Subtask 1 (30 điểm): $1 \le n \le 2000$, tổng $n$ trên tất cả các test case không vượt quá $10^4$ $(\sum_{i=1}^{q} n_i \le 10^4)$
- Subtask 2 (70 điểm): $1 \le n \le 10^5$, tổng $n$ trên tất cả các test case không vượt quá $5\cdot 10^5$ $(\sum_{i=1}^{q} n_i \le 5\cdot 10^5)$

## Output
Ứng với mỗi test case, bạn hãy đưa ra giá trị yêu cầu ở đề bài.

Bạn có thể xuất $t$ số nguyên trên cùng một dòng hoặc mỗi số trên một dòng.

## Test mẫu
### Input

4
4
1 2 3 4
3
1 1 1
1
2017
5
5 4 3 1 2

### Output

35
3
0
85

### Giải thích test mẫu
Với test case đầu tiên, giá trị cần tính là:
$a_1\cdot a_2+a_1\cdot a_3+a_1 \cdot a_4+a_2\cdot a_3+a_2\cdot a_4+a_3\cdot a_4$
$=\space 2+3+4+6+8+12=35$.

Với test case thứ hai, giá trị cần tính là:
$a_1\cdot a_2+a_1\cdot a_3+a_2\cdot a_3=1+1+1=3$.

Với test case thứ ba, vì $n=1$ nên không có cặp $(i, j)$ nào thoả mãn $1 \le i < j \le n$. Do đó, kết quả là $0$.