Nhập vào \(n\), in ra \(n\) số fibo đầu tiên.

Dãy Fibonacci \(1, 1, 2, 3, 5, 8, .....\)

Example

4

1 1 2 3

Cho một bảng số \(a\) nguyên kích thước \(m\cdot n\) và số nguyên \(k\). Hãy đếm xem trong dãy có bao nhiêu phần tử có giá trị \(k\).

Input

• Dòng 1: Gồm 2 số nguyên dương \(m, n\) và số nguyên \(k\).
• \(m\) dòng tiếp theo, mỗi dòng gồm \(n\) số

Output

• Kết quả bài toán

Constraints

• \(m,n\leq 10^3\)
• \(|k|\leq 10^3\)
• \(|a[i][j]|\leq 10^3\)

Example

2 3 4
2 4 6
6 4 2

2

Cho một số nguyên không âm N, hãy in ra chữ số đầu tiên của N.

Input Format

Số nguyên không âm N

Constraints

0≤n≤10^18

Output Format

In ra chữ số đầu tiên của N.

Sample Input 0

56721

Sample Output 0

5

Điều kiện thoả mãn dãy ngoặc đúng được định nghĩa như sau:

• Dãy rỗng "" là một dãy ngoặc đúng.
• Nếu dãy \(A\) là một dãy ngoặc đúng thì \((A)\) là một dãy ngoặc đúng.
• Nếu dãy \(A\) và dãy \(B\) là hai dãy ngoặc đúng thì \(A + B\) là một dãy ngoặc đúng.

Cho xâu \(s\) là một dãy ngoặc chỉ gồm 2 kí tự là \((\) và \()\), hãy kiểm tra xem xâu \(s\) có phải một dãy ngoặc đúng hay không.

Input

• Gồm một dòng chứa xâu ngoặc \(s\) \((1 \le |s| \le 10^3)\).

Output

• In ra Yes nếu xâu \(s\) là dãy ngoặc đúng, ngược lại in ra No.

Ví dụ

Input 1:

(()())

Output 1:

Yes

Input 2:

(()))

Output 2:

No

Cho dãy \(a\) có \(m\) số nguyên \(a_1, a_2, \ldots, a_m\).

Dãy \(b\) có \(n\) số nguyên \(b_1, b_2, \ldots, b_n\). Hãy tìm số lượng phần tử trong dãy \(a\) xuất hiện trong dãy \(b\).

Input

Dòng đầu tiên chứa hai số nguyên \(m\) và \(n\) \((0 < m, n \leq 10^5)\).

Dòng tiếp theo chứa \(m\) số nguyên \(a_i\) \((-10^9 \leq a_i \leq 10^9)\).

Dòng tiếp theo chứa \(n\) số nguyên \(b_i\) \((-10^9 \leq b_i \leq 10^9)\).

Output

Số lượng phần tử trong dãy \(a\) xuất hiện trong dãy \(b\).

Sample

Input

3 5
1 2 3
1 3 3 4 5

Output

2