Stop learning useless algorithms, go and solve some problems, learn how to use binary search 😈 - Um_nik

~x~ và ~y~ là hai số nguyên thoả mãn ~|x+y|=2023~.

Cho trước số nguyên ~x~. Hãy tìm ~y~ để ~x-y~ đạt giá trị nhỏ nhất.

Dữ liệu

Nhập vào số nguyên ~x~ ~(|x| \le 10^9)~.

Kết quả

In ra giá trị nhỏ nhất của ~x-y~.

Ví dụ

Input

1

Output

-2021

There are 10 types of people in this world: Those who understand binary and those who don't 😈

Cho số nguyên dương ~N~.

Hãy tính tổng của chữ số đầu tiên và chữ số cuối cùng của ~N~.

Dữ liệu

Nhập vào số nguyên dương ~N~ ~(N \le 10^9)~.

Kết quả

In ra một số nguyên là đáp án của bài toán trên.

Ví dụ

Input

29042024

Output

6

Ràng buộc

• Subtask ~1~ ~(60\%)~: ~N \le 100~.
• Subtask ~2~ ~(40\%)~: Không có ràng buộc gì thêm.

It's not a bug, it's a feature 😈

Cho số nguyên dương ~N~.

Hãy đếm số cặp số ~(x, y)~ nguyên dương thoả mãn:

• ~1\le x, y \le N~.
• ~x+y~ là số nguyên tố.

Dữ liệu

Nhập vào số nguyên dương ~N~ ~(1\le N \le 10^6)~.

Kết quả

In ra số cặp ~(x, y)~ thoả mãn

Ví dụ

Input

3

Output

5

Giải thích

Các cặp số ~(x, y)~ thoả mãn: ~(1, 1), (1, 2), (2, 1), (2, 3), (3, 2)~.

Ràng buộc

• Subtask ~1 \ (60\%)~: ~N \le 100~.
• Subtask ~2 \ (40\%)~: Không có ràng buộc gì thêm.

debugging /diːˈbʌɡɪŋ/ (v.): Being the detective in a crime movie where you are also the murderer.

MrTee đang có một dãy gồm ~N~ số nguyên dương ~a_1, a_2, \dots, a_N~ và cũng có một chiếc máy quét mới mua (ở Ý, rất đắt). Khi đặt chiếc máy quét vào vị trí thứ ~i~, chiếc máy sẽ hiện số lượng các số mà bằng với ~a_i~ trong dãy mà có khoảng cách tới ~i~ không quá ~K~, kể cả chính nó. Vì quá mệt mỏi vì học sinh quá báo trong kì thi vừa rồi, MrTee đã nhờ bạn giúp MrTee thử chiếc máy này xem ở mỗi vị trí ~i~ từ ~1~ đến ~N~, chiếc máy sẽ trả về giá trị bao nhiêu.

Nói cách khác, cho một dãy ~N~ số nguyên dương ~a_1, a_2, \dots, a_N~, với mỗi ~i~, bạn cần tìm số lượng số ~j~ thỏa mãn ~a_i = a_j~ và ~|i - j| \le K~ ~(1 \le i, j \le N)~.

Liệu bạn có phải pro player hay cũng báo thầy như học sinh của MrTee?

Input

• Dòng đầu tiên gồm hai số nguyên dương ~N, K~ ~(K \le N)~.
• Dòng thứ hai gồm ~N~ số nguyên dương ~a_1, a_2, \dots, a_N~ ~(1 \le a_i \le 10^5)~.

Output

• Gồm một dòng gồm ~N~ số nguyên, số thứ ~i~ là đáp án nếu ta đặt máy quét vào vị trí thứ ~i~.

Scoring

• Subtask 1 ~(60 \%)~: ~K \le N \le 2000~.
• Subtask 2 ~(40 \%)~: ~K \le N \le 10^5~.

Sample Input

6 2
1 1 2 2 2 1

Sample Output

2 2 3 3 3 1

It works … on my machine 😈

Cho bốn số nguyên ~n, x, y, m~. Dãy số ~A~ có độ dài ~n~ được tạo ra theo cách sau:

• ~a_1 = x~;
• ~a_i = (a_{i-1}*x+y) \% m~ với ~2 \le i \le n~.

Dãy số ~B~ là dãy số ~A~ sau khi sắp xếp không giảm.

Tính: ~\sum_{i=1}^{n} (b_i * i) \% m~

Input:

• Gồm một dòng chứa bốn số nguyên ~n, x, y, m~ ~(1 \le x, y \le m)~.

Output:

• In ra một số nguyên là kết quả của bài toán.

Scoring:

• Subtask ~1~ ~(40\%)~: ~n \le 10^5; m \le 10^9~;
• Subtask ~2~ ~(40\%)~: ~n \le 3*10^7; m \le 3*10^7~;
• Subtask ~3~ ~(20\%)~: ~n \le 10^{18}; m \le 10^6~;

Sample Input

3 2 1 10

Sample Output

0

Note

• Dãy số ~A~: ~2, 5, 1~;
• Dãy số ~B~: ~1, 2, 5~;
• Kết quả: ~(1*1+2*2+5*3)\%10=0~.