Có một con đường được ghép từ n đoạn thẳng liên tiếp, mỗi đoạn có chiều dài d và bề rộng không đổi là r. Giữa hai đoạn liên tiếp có một khúc cua vuông góc. Con đường không khép kín và không tự cắt.

Yêu cầu: Tính diện tích mặt đường.

Input

• Một dòng gồm ba số nguyên n, d, r (1 ≤ n, d, r ≤ 10^5, r <= d).

Output

• Một số nguyên duy nhất là diện tích mặt đường.

Sample Input 1

3 20 3

Sample Output 1

162

Cho 1 số nguyên n (Với 1≤n≤1000). Tính tổng các số nguyên từ 1 đến n.

Input

Dòng đầu tiên có chứa 1 số nguyên n (Với 1≤n≤1000).

Output

Một dòng duy nhất là 1 số là tổng các số nguyên từ 1 đến n.

Simple Examples

Input

1

Output

1

Input

3

Output

6

Cho 1 số nguyên n (Với 1≤n≤10^9). Tính tổng các số nguyên từ 1 đến n.

Input

Dòng đầu tiên có chứa 1 số nguyên n (Với 1≤n≤10^9).

Output

Một dòng duy nhất là 1 số là tổng các số nguyên từ 1 đến n.

Simple Examples

Input

1

Output

1

Input

3

Output

6

Ngày xửa ngày xưa, trong một vương quốc nọ có một cô công chúa xinh đẹp. Kluco muốn lấy cô công chúa xinh đẹp đó chỉ khi anh ấy trả lời được câu hỏi của nhà vua. Nhà vua cho anh ấy một số nguyên ~n~ và yêu cầu anh ấy viết ra số đảo ngược của nó. Là một lập trình viên tài ba, bạn hãy giúp Kluco lấy được cô công chúa xinh đẹp nhé!

Nhiệm vụ của bạn là viết chương trình mô phỏng chiếc gương thần kỳ này.

Input

• Một số nguyên dương ~n~ (~1 \leq n \leq 10^9~).

Output

• Số nguyên là kết quả khi viết ~n~ lên gương thần kỳ.

Sample Input 1

1234

Sample Output 1

4321

Sample Input 2

790

Sample Output 2

97

Một bài toán thực tế áp dụng toán học và tin học mà bạn Tèo đố bạn Tí mà bạn Tí phải trằn trọc suy nghĩ, không làm sao giải được hết Test Case của bài tập này. Vấn đề khá dễ hiểu, Tèo cho bạn Tí một số nguyên dương n và một bóng đèn đang tắt. Bạn Tí này phải đếm các số từ 1 đến n sao cho mỗi lần đến số thứ i là ước của n thì bạn Tí sẽ thay đổi trạng thái của bóng đèn (Bật sang tắt hoặc tắt sang bât). Nhưng vì số quá lớn và bạn Tí cũng không có nhiều thời gian để giải quyết bài này. Bạn có thể trả lời giúp Tí rằng bóng đèn có đang bật (sáng) hay không?

Input

Một dòng duy nhất chứa một số nguyên n.

Subtask 1 (40% số điểm): n ≤ ~10^6~

Subtask 2 (40% số điểm): n ≤ ~10^{9}~

Subtask 2 (20% số điểm): n ≤ ~10^{18}~

Output

Nếu bóng đèn được bật sau khi đếm xong, thì in ra "YES" ngược lại in "NO".

Examples

Input

8

Output

NO

Bạn đang ở trên một đường thẳng và xuất phát từ điểm 0. Mục tiêu là đến được điểm n. Trong một giây bạn có thể di chuyển 2 hoặc 3 bước sang trái hoặc phải (chính xác hơn là điểm hiện tại của bạn là x, thì bạn có thể di chuyển đến điểm ~x - 2, x - 3, x + 2, x + 3~. Tính số giây ít nhất để đến được điểm n.

Input

Một dòng duy nhất chứa một số nguyên (1 ≤ ~n ≤ 10^{15}~).

Output

Một dòng duy nhất là giây ít nhất để đi từ điểm 0 đến được điểm n.

*Example 1 *

Input

4

Output

2

*Example 2 *

Input

9 

Output

3 

*Example 3 *

Input

11 

Output

4 

Viết chương trình tính giai thừa n!

Input Input một dòng duy nhất số nguyên n (n≤15)

Output
Output một dòng duy nhất giá trị giai thừa của số nguyên n

Examples

Input

4

Output

24 

Cho mảng a gồm có n phần tử ~a_0~, ~a_1~, ... ~a_{n-1}~ và một số nguyên k. Hãy in ra phần tử lớn thứ k của mảng a sau khi đã sắp sếp tăng dần.

Lưu ý là chỉ số bắt đầu từ 0.

Input

Gồm 2 dòng:

Dòng thứ nhất là số phần tử của mảng n và số k (~1 ≤ n ≤ 10^3~, 0 ≤ k ≤ n-1)

Dòng thứ hai gồm n số nguyên ~a_0~, ~a_1~, ... ~a_{n-1}~.

Output

Một dòng duy nhất là số lớn thứ k của mảng a.

Examples

Input

8 3  
4 2 6 3 6 4 5 7 

Output

4 

Mảng sau khi đã sắp sếp tăng dần là: 2, 3, 4, 4, 5, 6, 6, 7. Vì vậy phần tử lớn thứ 3 là 4 (chỉ số bắt đầu từ 0)

Tại một vương quốc xa xôi, có một vị vua bất tài tên là Kluco. Hắn đã tước đoạt toàn bộ của cải của người dân, và bạn là một trong những nạn nhân của sự bóc lột tàn nhẫn đó. Nổi tiếng trong vùng với sự thông minh và tài năng toán học, bạn trở thành mục tiêu của Kluco. Khi không còn gì để chiếm đoạt, Kluco đã ra lệnh cho binh lính bắt bạn và đưa về cung điện của hắn để giải một loạt bài toán mà hắn tự cho là rất khó.

Tuy nhiên, vua KhangKoii của nước láng giềng, không thể chịu đựng được sự nhẫn tâm của Kluco, và quyết tâm cứu bạn. Để làm được điều này, bạn cần phải giải một bài toán để lấy được mật mã mở khóa và thông báo cho KhangKoii các cổng đã được giải mã, giúp vị vua này xâm nhập vào cung điện và đối phó với Kluco.

Tại khu vực giam giữ, bạn chỉ có thể mở khóa cánh cổng bằng cách giải một bài toán toán học. Bạn được cung cấp ba số nguyên a, b, và c với điều kiện ~( |a|, |b|, |c| \le10^{18} )~. Nhiệm vụ của bạn là xác định xem có số nào trong ba số này có phải là tổng của hai số còn lại hay không.

* Input *

• Ba số nguyên a, b, và c.

* Output *

• Nếu có ít nhất một số là tổng của hai số còn lại, in "YES". Dòng tiếp theo in hai số mà tổng của chúng là số còn lại (theo thứ tự tăng dần).
• Ngược lại, in "NO".

Sample Input

1 -4 5

Sample Output

YES
-4 5

Hôm nay trời mưa lớn. Vì khá lười nên AliVu quyết định chạy bộ cho trời bớt mưa. Đường đua hôm nay là 1 vòng tròn lớn, trên vòng tròn có các số đánh dấu từ 1 tới n được nối đuôi nhau tạo thành 1 chu kì, AliVu tự hỏi nếu AliVu xuất phát từ đỉnh 1 đi theo hướng cùng chiều kim đồng hồ thì sau k bước đi AliVu đang ở con số mấy??

INPUT

Dòng đầu tiên chứa số nguyên n (~1 \leq n \leq 10^6~)

Dòng tiếp theo chứa số nguyên k (~1 \leq k \leq 10^{18}~)

OUTPUT

Một số duy nhất là đáp án của đề bài

SAMPLE INPUT 1

2 5

SAMPLE OUTPUT 1

2

SAMPLE INPUT 2

3 10

SAMPLE OUTPUT 2

2

Hoan thực sự rất thích toán. Một ngày nọ, khi đang giải một bài toán khác, anh ấy nghĩ ra một cái cây khá thú vị. Cây này được xây dựng như sau:

Ban đầu chỉ có một đỉnh mang số 1 là gốc cây. Sau đó Hoan thêm 2 đỉnh con vào sau gốc và gán 2 số liên tiếp là 2 và 3 tương ứng. Sau đó Hoan lại thêm các phần tử con vào các đỉnh theo thứ tự số lượng tăng dần bắt đầu từ 2, gán cho đỉnh con các số chưa được sử dụng lớn hơn 0. Kết quả là Hoan đã có một cây nhị phân vô hạn với đỉnh gốc là 1, với mỗi đỉnh có 2 đỉnh con và số đỉnh được sắp xếp tuần tự theo từng lớp. như hình bên dưới:

Hoan tự hỏi tổng các giá trị các đỉnh trên đường đi từ đỉnh 1 tới đỉnh x là bao nhiêu?. Vì Hoan khá lười nên anh ấy đã nhờ bạn giúp anh ấy tìm tổng đó.

INPUT

Dòng đầu tiên chứa số nguyên n là đỉnh mà Hoan muốn tính (~1 \leq n \leq 10^{18}~)

OUTPUT

Một số nguyên duy nhất là tổng mong muốn

SAMPLE INPUT 1

1

SAMPLE OUTPUT 1

1

SAMPLE INPUT 2

6

SAMPLE OUTPUT 2

10

giải thích test đề: ở test 1 có thể thấy từ đỉnh 1 tới đỉnh 1 thì chỉ có duy nhất 1 đỉnh mang giá trị 1 nên kết quả là 1

ở test 2 có thể thấy từ đỉnh 1 tới đỉnh 6 có 3 đỉnh là 1,3,6 và tổng cần tìm là 1 + 3 + 6 = 10.

Viết chương trình để xác định xem một số đã cho có phải là số nguyên tố hay không.

Input

Input một dòng duy nhất số nguyên n (1≤100000)

Output

Output một dòng duy nhất kết quả số n là số nguyên tố hay không ?

Nếu n là số nguyên tố thì in "YES", ngược lại in "NO".

Examples

Input

3

Output

YES

Input

4

Output

NO

Giới thiệu: Đây là đề Training Python 2

Để đạt được học bổng cần xếp loại điểm rèn luyện từ mức khá trở lên. Các bạn hãy giúp Nhân và các bạn của mình kiểm tra xếp loại điểm rèn luyện của mình nhé.

Đầu vào là một số nguyên ~n~ người và các số nguyên ~a~, ~b~.

Với ~a~ là số điểm được đoàn trường đánh giá, ~b~ là số điểm thưởng đạt được.

Biết điểm rèn luyện được đánh giá như sau:

Từ ~0~ đến dưới ~30~ xếp loại Kém

Từ ~30~ đến dưới ~50~ xếp loại Yếu

Từ ~50~ đến dưới ~65~ xếp loại Trung bình

Từ ~65~ đến dưới ~80~ xếp loại Khá

Từ ~80~ đến ~100~ xếp loại Giỏi

Nếu không thuộc trường hợp nào ở trên in ra Error

Input

Dòng đầu tiên là ~n~

~n~ dòng tiếp theo là các số ~a~ ~b~ cho mỗi trường hợp

Output

~n~ dòng là đánh giá điểm rèn luyện của ~n~ bạn trên

Examples

Input

3
30 10
60 25
80 30

Output

Yếu
Giỏi
Error

Mô tả vấn đề

Viết chương trình nhập 2 số nguyên dương, tìm ước số chung lớn nhất (gcd - greatest common divisor) và bội số chung nhỏ nhất (lcm - least common multiple)  của chúng.

Input

Nhập 2 số nguyên dương a và b (1 ≤ a, b ≤ 10~^5~)

Output

In ra ước chung lớn nhất và bội chung nhỏ nhất

Sample Input 1

2 4

Sample Output 1

2 4

Cho hình xoắn ốc như sau có ô trên cùng bên trái là 1.

Nhiệm vụ của bạn là tìm ra số ở vị trí hàng x cột y.

Input

Một dòng duy nhất chứa hai số nguyên x và y (x, y ≤ ~10^9~).

Output

Một dòng duy nhất là số nguyên trong hình xoắn ốc ở hàng x cột y.

*Example 1 *

Input

3 4 

Output

12 

*Example 2 *

Input

5 3

Output

19  

Cho 2 số nguyên dương x,y (Với 1≤x,y≤10000) là độ dài 2 cạnh của 1 tờ bìa cứng. Với tấm bìa cứng đó bạn hãy cắt thành hình chữ thập như trong hình và gấp lại thành hình hộp chữ nhật không nắp a∗b∗h. Hỏi thể tích lớn nhất của hình hộp chữ nhật a∗b∗h mà bạn có thể tạo ra là bao nhiêu?

Input

Dòng đầu tiên có chứa 2 số nguyên dương x,y (Với 1≤x,y≤10000).

Output

Một dòng duy nhất là 1 số đại diện cho giá trị của thể tích lớn nhất của hình hộp chữ nhật a∗b∗h mà bạn có thể tạo ra. Kết quả làm tròn đến 1 chữ số thập phân.

Simple Examples

Input

1 1

Output

0.0

Input

3 1

Output

0.3

Input

9 3

Output

8.5

Sau những giờ học thuật toán căng thẳng tại H3.2. Phú và Tài quyết định chơi một ván cờ tướng để giải trí. Tuy nhiên, sau 100 nước thì Phú đã dồn Tài vào thế khó và chỉ còn 2 con mã. Bây giờ Tài đã căng rồi lại càng cảm thấy căng thẳng hơn. Tài muốn chiến thắng nên đã tính tất cả các nước mà 2 con mã có thể đi để tìm được nước đi tiếp theo để có khả năng chiến thắng là cao nhất và hai con mã này không được tấn công nhau. Hãy giúp Tài tính tất cả các trường hợp trên.

Cụ thể, cho bàn cờ có kích thước n x n. Hãy đếm số cách đặt 2 con mã sao cho chúng không tấn công nhau.

Trên bàn cờ thì một quân mã ở ô (x, y) có thế tấn công 8 ô (x-1, y-2), (x-2, y-1), (x-2, y+1), (x-1, y+2), , (x+1, y+2), (x+2, y+1), (x+2, y-1), , (x+1, y-2)

Input

Một dòng duy nhất chứa một số nguyên n

Output

Một dòng duy nhất là số cách đặt 2 con mã sao cho chúng không tấn công nhau.

*Example 1 *

Input

2

Output

6 

Note: Các cách đặt 2 quân mã là:

(1, 1) và (1, 2)

(1, 1) và (2, 1)

(1, 1) và (2, 2)

(1, 2) và (2, 1)

(1, 2) và (2, 2)

(2, 1) và (2, 2)

Example 2

Input

3 

Output

28 

HoNhatTruong đang học về số nguyên tố. Bạn ấy muốn biết sau một số nguyên dương n, thì số nguyên tố tiếp theo là bao nhiêu.

Hãy viết chương trình nhập vào số n (1 ≤ n ≤ 10^6) và in ra số nguyên tố nhỏ nhất lớn hơn n.

Input

• Một số nguyên dương n.

Output

• Một số nguyên duy nhất là số nguyên tố nhỏ nhất lớn hơn n.

Sample Input 1

7

Sample Output 1

11

Sample Input 2

20

Sample Output 2

23

hpgiakhang1405 là một người thích sự hoàn hảo (có lẽ thế :v). Vì thế khi anh ấy thấy một con số không hoàn hảo thì trong ngày hôm ấy anh ấy sẽ không có mood làm gì cả. Bạn hãy xem rằng trong ngày hôm nay anh ấy có bị tụt mood không nhé.

Một số hoàn hảo được định nghĩa là tổng các ước của nó (ngoại trừ chính nó) bằng chính số đó.

Ví dụ:

• 6 = 1 + 2 + 3.

Hãy viết chương trình kiểm tra một số nguyên dương ~n~ (~1 \leq n \leq 10^6~) có phải là số hoàn hảo hay không.

Input

• Một số nguyên dương ~n~.

Output

• In ra "YES" nếu ~n~ là số hoàn hảo.
• In ra "NO" nếu không phải.

Sample Input 1

6

Sample Output 1

YES

Sample Input 1

12

Sample Output 1

NO

hpgiakhang1405 là một người thích sự hoàn hảo (có lẽ thế :v). Vì thế khi anh ấy thấy một con số không hoàn hảo thì trong ngày hôm ấy anh ấy sẽ không có mood làm gì cả. Bạn hãy xem rằng trong ngày hôm nay anh ấy có bị tụt mood không nhé.

Một số hoàn hảo được định nghĩa là tổng các ước của nó (ngoại trừ chính nó) bằng chính số đó.

Ví dụ:

• 6 = 1 + 2 + 3.

Hãy viết chương trình kiểm tra một số nguyên dương ~n~ (~1 \leq n \leq 10^{14}~) có phải là số hoàn hảo hay không.

Input

• Một số nguyên dương ~n~.

Output

• In ra "YES" nếu ~n~ là số hoàn hảo.
• In ra "NO" nếu không phải.

Sample Input 1

6

Sample Output 1

YES

Sample Input 1

12

Sample Output 1

NO

Trong lớp Training K20 của CLB H3.2PL hiện tại có ~n~ học viên với mỗi học viên có chỉ số sức mạnh là ~a_i~.

Một hôm, mentor điển trai AliVu đưa ra một trò chơi như sau: AliVu có tổng cộng ~q~ cơ hội tăng chỉ số sức mạnh cho các học viên, với mỗi cơ hội ~q_i~ có một số ~x_i~ là chỉ số sức mạnh được tăng thêm cho bạn học viên nào được chọn. Tuy nhiên vì mong muốn cả lớp có sự công bằng nên với mỗi cơ hội, AliVu sẽ chọn ra bạn nào có chỉ số sức mạnh thấp nhất lớp hiện tại và tăng sức mạnh thêm cho bạn ấy một lượng là ~x_i~.

Vì số lượng là quá lớn, AliVu không thể biết đến cuối cùng, sau khi trao hết cơ hội cho các bạn thì bạn nào có chỉ số sức mạnh thấp nhất lớp hiện tại. Bạn hãy tính toán giúp AliVu nhé!

Input

• Dòng đầu tiên số nguyên ~n~ ~(1 \leq n \leq 2 \times 10^5)~ ~-~ số lượng học viên trong lớp.
• Dòng tiếp theo chứa ~n~ số nguyên không âm ~a_i~ ~(0 \leq a_i \leq 10^9)~ ~-~ chỉ số sức mạnh của các học viên.
• Dòng tiếp theo chứa số nguyên ~q~ ~(1 \leq q \leq 2 \times 10^5)~ ~-~ số lượng cơ hội tăng sức mạnh.
• ~q~ dòng tiếp theo chứa các số ~x_i~ ~(1 \leq x_i \leq 10^9)~ ~-~ chỉ số sức mạnh được tăng thêm trong mỗi cơ hội.

Output

Một dòng duy nhất là chỉ số sức mạnh thấp nhất lớp sau khi đã thực hiện hết toàn bộ cơ hội tăng sức mạnh.

Sample Input

3
1 1 2
3
2
1
2

Sample Output

2

Hôm nay là 1 ngày đẹp trời, Kluco vừa học xong cách đếm số, cô giáo hpgiakhang1405 đã cho Kluco 1 bài tập đếm số như sau:

Cô giáo cho Kluco ~n~ số tự nhiên và ~q~ câu hỏi. Với mỗi câu hỏi chứa 1 số tự nhiên ~q_i~, Kluco sẽ phải đếm số lượng số lượng phần tử ~q_i~ có trong ~n~ số tự nhiên đã cho.

Vì cô giáo này là ác quỷ, nên số lượng số quá nhiều khiến Kluco choáng váng, nên anh ấy đã nhờ bạn giúp anh ấy hoàn thành bài tập này.

Input

• Dòng đầu tiên số nguyên ~n~ ~(1 \leq n \leq 2 \times 10^5)~.
• Dòng tiếp theo chứa ~n~ số nguyên dương ~a_i~ ~(-10^9 \leq a_i \leq 10^9)~.
• Dòng tiếp theo chứa số nguyên ~q~ ~(1 \leq q \leq 2 \times 10^5)~.
• ~q~ dòng tiếp theo chứa các số ~q_i~ ~(-10^9 \leq q_i \leq 10^9)~.

Output

• ~q~ dòng là số lượng số ~q_i~ có trong ~n~ số tự nhiên đã cho.

Sample Input

3
1 1 2
3
1
2
3

Sample Output

2
1
0

Ba người chơi một trò chơi như sau: mỗi người viết ra ~n~ từ khác nhau, mỗi từ có độ dài ~3~ ký tự. Sau đó, họ tính tổng điểm theo quy tắc sau:

• Nếu một từ chỉ được viết bởi một người ~-~ người đó nhận được 3 điểm.
• Nếu một từ được viết bởi hai người ~-~ mỗi người trong hai người đó nhận 1 điểm.
• Nếu một từ được viết bởi cả ba người ~-~ không ai nhận được điểm nào.

Kết thúc trò chơi, hỏi tổng điểm của ba người là bao nhiêu (số điểm ban đầu của cả ba đều bằng ~0~)?

Input

• Dòng đầu tiên số nguyên ~n~ ~(1 \leq n \leq 10^4)~ ~-~ số lượng từ được viết ra bởi mỗi người.
• Ba dòng tiếp theo, mỗi dòng chứa ~n~ từ khác nhau ~-~ các từ được viết bởi mỗi người. Mỗi từ bao gồm ~3~ ký tự tiếng Anh viết thường.

Output

Một dòng gồm ba số nguyên là số điểm của ba người chơi (theo thứ tự người chơi tăng dần).

Sample Input 1

1
abc
def
abc

Sample Output 1

1 3 1

Sample Input 2

3
orz for qaq
qaq orz for
cod for ces

Sample Output 2

2 2 6

Sample Input 3

5
iat roc hem ica lly
bac ter iol ogi sts
bac roc lly iol iat

Sample Output 3

9 11 5

Một từ hoặc câu được gọi là pangram nếu nó chứa tất cả các chữ cái của bảng chữ cái trong ngôn ngữ đó ít nhất một lần. Pangram thường được sử dụng để thử nghiệm kiểu chữ trong in ấn và thiết bị đầu ra.

Bạn có một chuỗi gồm các chữ cái Latin viết hoa và viết thường. Hãy kiểm tra xem chuỗi này có phải là pangram hay không. Một chữ cái được coi là có mặt trong chuỗi nếu nó xuất hiện dưới dạng viết hoa hoặc viết thường.

Input

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 100)~ - độ dài của chuỗi cần kiểm tra.
• Dòng thứ hai bao gồm một chuỗi chứa các chữ cái Latin viết hoa và viết thường.

* Output *

• In YES nếu chuỗi là pangram, ngược lại in NO.

Sample Input 1

26
MGJYIZDKsbhpVeNFlquRTcWoAx

Sample Output 1

YES

Giới thiệu: Đây là đề Training Python 3

Nam hay sử dụng mạng xã hội để giết thời gian. Trong trang danh sách trò chuyện, khi Nam gửi tin nhắn đến một người bạn nào đó, thì cuộc trò chuyện của người bạn đó sẽ xuất hiện ở đầu trang. Thứ tự đối với các cuộc trò chuyện khác không thay đổi. Trong trường hợp nếu không có cuộc trò chuyện nào với người bạn này trước đó, thì cuộc trò chuyện mới sẽ được chèn vào đầu danh sách trò chuyện.

Giả sử rằng Nam chưa có cuộc trò chuyện nào trước đó, và Nam tạo một danh sách các cuộc trò chuyện sau khi tất cả các tin nhắn của anh ấy đã được gửi đi thành công. Giả sử không có người bạn nào nhắn bất kì tin nhắn nào cho Nam.

Input

Dòng đầu tiên chứa 1 số ~n~ ~(1 \le n \le 200 000)~ - số tin nhắn mà Nam gửi.

~n~ dòng tiếp theo hiển thị người nhận tin nhắn được sắp xếp theo thứ tự tin nhắn được gửi. Tên của mỗi người tham gia cuộc trò chuyện là một dãy kí tự gồm các chữ cái tiếng Anh viết thường có độ dài tối đa là ~10~ kí tự.

Output

In tất cả những người mà Nam đã nói chuyện theo thứ tự các cuộc trò chuyện từ trên xuống dưới.

Examples 1

Input

4
alex
ivan
roman
ivan

Output

ivan
roman
alex

Examples 2

Input

8
alina
maria
ekaterina
darya
darya
ekaterina
maria
alina

Output

alina
maria
ekaterina
darya

Note

Trong test case 1, Nam gửi tin nhắn cho bạn có tên "alex", danh sách chat của Nam sẽ hiển thị như sau:

1. alex

Sau đó Nam gửi tin nhắn cho bạn "ivan", danh sách chat của Nam sẽ hiển thị như sau:

1. ivan
2. alex

Nam gửi tin nhắn thứ 3 cho người bạn tên "roman", danh sách trò chuyện của Nam sẽ được hiển thị như sau:

1. roman
2. ivan
3. alex

Nam viết tin nhắn thứ tư cho bạn bè bằng tên "ivan", cho người mà anh ta đã gửi tin nhắn, vì vậy danh sách các cuộc trò chuyện thay đổi như sau:

1. ivan
2. roman
3. alex

Trong giờ học lập trình, thầy giáo Nghialaptrinh giao cho lớp một bài tập về dấu ngoặc. ctanh2610dona thì rất nghiêm túc, còn Godsent thì nghịch ngợm, suốt ngày ghép dấu ngoặc lung tung. Một hôm, ctanh2610dona viết lên bảng một chuỗi toàn dấu ngoặc ( và ), rồi hỏi Godsent: "Ê Bảo, chuỗi này có hợp lệ không?". Anh ấy nghe xong nhưng không hiểu, liền quay sang cầu cứu bạn. Bạn hãy giúp anh ấy nhé!

Biết rằng chuỗi ngoặc hợp lệ nghĩa là:

1. Mỗi dấu ngoặc mở ( đều phải có một dấu ngoặc đóng ) đi kèm.
2. Không được có ngoặc đóng ) xuất hiện trước ngoặc mở (.

Input

• Một chuỗi chỉ gồm các ký tự ( và ), độ dài ≤ 10^5.

Output

• In ra "YES" nếu chuỗi hợp lệ.
• In ra "NO" nếu chuỗi không hợp lệ.

Ví dụ

Input 1

(()())

Output 1

YES

Input 1

())(

Output 1

NO

Ở một vương quốc nọ vô cùng rộng lớn có diện tích ~N \times M~ hẹt ta nhưng lại được cai trị bởi một vị vua bất tài tên là Kluco, vì sự kém cỏi của mình nên vương quốc thường xuyên bị các thế lực đen tối xâm chiếm và c.ư.ớ.p bóc, để an toàn Kluco đã phân bổ đều các thành phố trên toàn bộ lãnh thổ để giảm thiểu thiệt hại khi bị các thế lực khác xâm lược nên cứ mỗi 1 hẹt ta vuông thì sẽ mọc lên 1 thành phố ở trung tâm.

Vào một ngày nọ ma vương unKluco là một phiên bản Kluco hắc ám tới từ một vũ trụ song song và thấy vô cùng ngứa mắt với cách phân bổ này của Kluco nên unKluco đã tấn công vào vương quốc của Kluco để bóc lột, nếu không đưa đủ vàng thì unKluco sẽ xoá sổ toàn bộ vương quốc.

Ma vương unKluco rất ghét hình vuông nên đã đề nghị cứ mỗi bốn thành phố riêng biệt tạo nên một hình vuông hoàn chỉnh thì unKluco sẽ thu của Kluco ~1~ thỏi vàng. Vì bất tài nên Kluco cũng chả giỏi tính toán, trong lúc không thể tính được số vàng phải trả là bao nhiêu thì Kluco nhớ ra rằng vương quốc mình dẫn còn một lập trình viên tài ba đó chính là bạn.

Bạn hãy giúp Kluco pha này nhé, biết rằng ~1 \leq N,M \leq 2*10^5~ và unKluco không mang túi 9 gang nên chỉ nhận số vàng đã chia dư cho ~10^9 + 7~

Input

• Hai số nguyên ~N,M (1 \leq N,M \leq 2*10^5)~ , đại diện cho chiều dài và chiều rộng của vương quốc.

Output

• Một số nguyên duy nhất là số thỏi vàng unKluco nhận được.

Sample Input

3 3

Sample Output

6

Giới Hạn

• Có 20% số test với ~N, M \leq 10~
• Có 20% số test với ~N, M \leq 100~
• Có 20% số test với ~N, M \leq 300~
• Có 20% số test với ~N, M \leq 10^3~
• Còn lại không có ràng buộc nào