Trong mặt phẳng Oxy, cho ba điểm không trùng nhau và không cùng nằm trên một đường thẳng, tạo thành một tam giác: ~A~ có tọa độ ~(x_1, y_1)~, ~B~ có tọa độ ~(x_2, y_2)~, ~C~ có tọa độ ~(x_3, y_3)~. Viết chương trình kiểm tra xem tam giác ~ABC~ có phải là tam giác vuông hay không?

INPUT

Nhập từ bàn phím gồm ~6~ số nguyên: ~x_1, y_1, x_2, y_2, x_3, y_3~ (~-10^9 \leq x_1, y_1, x_2, y_2, x_3, y_3 \leq 10^9~)

OUTPUT

Xuất ra màn hình thông báo TAM GIAC VUONG nếu kiểm tra tam giác ~ABC~ là tam giác vuông, ngược lại ghi KHONG PHAI TAM GIAC VUONG.

SAMPLE INPUT 1

1 1 5 1 1 7

SAMPLE OUTPUT 1

TAM GIAC VUONG

SAMPLE INPUT 2

1 1 9 2 4 3

SAMPLE OUTPUT 2

KHONG PHAI TAM GIAC VUONG

Viết chương trình tính giá trị biểu thức:

$$S = 1 + 3 + 5 + ... + (2n - 1)$$

INPUT

Số tự nhiên ~n~ (~3 < n < 10^9~).

OUTPUT

Giá trị biểu thức ~S~ tìm được.

SAMPLE INPUT 1

5

SAMPLE OUTPUT 1

25

SAMPLE INPUT 2

86

SAMPLE OUTPUT 2

7396

Một xâu ký tự có thể "nén" theo cách sau: xâu con gồm ~n > 1~ ký tự giống nhau, chẳng hạn gồm ~5~ kí tự a sẽ được ghi thành 5a. Ví dụ xâu egddddHHk sẽ được nén thành eg4d2Hk Hãy viết chương trình nén xâu ký tự cho trước.

INPUT

Xâu dài không quá ~256~ ký tự (xâu chỉ bao gồm các ký tự chữ cái).

OUTPUT

Xâu nén tìm được.

SAMPLE INPUT 1

egddddHHk

SAMPLE OUTPUT 1

eg4d2Hk

SAMPLE INPUT 2

aBcdeEf

SAMPLE OUTPUT 2

aBcdeEf

Chữ số cuối cùng của một số có ít nhất hai chữ số là phần dư của phép chia số đó cho ~10~. Ví dụ số ~64859~ có chữ số cuối cùng là ~9~.

Viết chương trình tìm chữ số cuối cùng của một số.

INPUT

Nhập từ bàn phím hai số tự nhiên ~N~ và ~M~ (~1 < N, M < 10^9~).

OUTPUT

Xuất ra màn hình kết quả là chữ số cuối cùng của số ~N^M~ (giá trị của ~N~ mũ ~M~).

SAMPLE INPUT 1

5 6

SAMPLE OUTPUT 1

5

SAMPLE INPUT 2

38 12

SAMPLE OUTPUT 2

6

Cho một số tự nhiên ~N~, ta có một dãy số ~A~ gồm các số tự nhiên từ 1 đến ~N~.

Phép nén dãy số là tạo ra dãy số mới mà các phần tử được tạo ra bằng cách lần lượt cộng hai số cạnh nhau của dãy số ban đầu. Mỗi lần nén dãy số, dãy số mới sẽ ít hơn dãy số trước một phần tử. Ta nén dãy số đến khi còn một phần tử, phần tử đó là giá trị nén của dãy số.

Ví dụ: với ~N = 4~ ta có kết quả cuối cùng là số ~20~:

Dãy ban đầu: ~1\ 2\ 3\ 4~
Nén lần 1: ~3\ 5\ 7~
Nén lần 2: ~8\ 12~
Nén lần 3: ~20~

Viết chương trình xuất ra giá trị nén của dãy số. Vì kết quả có thể rất lớn, nên chỉ cần xuất ra số dư của phép chia giá trị nén của dãy số cho ~1000000000~ (hay ~10^9~).

INPUT

Nhập từ bàn phím giá trị của số ~N~ ~(1 < N < 400)~.

OUTPUT

Xuất ra màn hình kết quả là số dư của phép chia giá trị nén của dãy số cho ~1000000000~ (hay ~10^9~).

SAMPLE INPUT 1

4

SAMPLE OUTPUT 1

20

SAMPLE INPUT 2

15

SAMPLE OUTPUT 2

131072