Tin học trẻ bảng B - Nghệ An

Ba anh em An, Bình, Phúc được mẹ mua cho ba hộp bi có số viên bi tương ứng là \(a, b, c\) (số bi trong mỗi hộp khác nhau). Bình biết anh An sẽ nhường cho mình lấy hộp có số bi nhiều hơn và Bình cũng sẽ nhường em Phúc hộp có số bi nhiều nhất.

Hãy viết chương trình nhập vào ba số nguyên có giá trị đôi một khác nhau tương ứng với số bi trong ba hộp mà mẹ mua, chương trình sẽ trả về số bi mà Bình được nhận. (Số bi trong mỗi hộp không vượt quá \(100\))

Example

5 3 4

4

Cho một dãy số nguyên dương gồm \(N\) phần tử. Từ dãy số đó, hãy xoá đi ít phần tử nhất để các phần tử còn lại thoả mãn tính chất sau: với mỗi hai phần tử \(x, y\) bất kì trong dãy còn lại, \(x\) chia hết cho \(y\) hoặc \(y\) chia hết cho \(x\).

Yêu cầu: Cho dãy số nguyên gồm \(N\) phần tử, đếm số lượng phần tử cần xoá đi ít nhất để thoả mãn yêu cầu bài toán.

Input

Vào từ thiết bị nhập chuẩn theo khuôn dạng:

• Dòng đầu tiên chứa số nguyên dương \(N\);
• Dòng thứ hai chứa \(N\) số nguyên dương, các số cách nhau bởi dấu cách và có giá trị không vượt quá \(10^6\).

Output

• Ghi ra thiết bị ra chuẩn một số nguyên duy nhất – số lượng phần tử cần xoá đi ít nhất để thoả mãn yêu cầu bài toán.

Scoring

• Subtask #1 (\(50\%\) số điểm): \(N \leq 20\);
• Subtask #2 (\(30\%\) số điểm): \(N \leq 5000\);
• Subtask #3 (\(20\%\) số điểm): \(N \leq 10^6\);

Example

5
6 16 3 2 4

2

Lớp Hồng đang chơi trò tô màu trên bảng số. Các bạn kẻ một bảng số hình chữ nhật gồm \(N\) dòng và \(M\) cột. Các hàng được đánh số từ 1 đến \(N\), từ trên xuống dưới; các cột được đánh số từ 1 đến \(M\), từ trái sang phải. Ô ở hàng thứ \(i\) và cột thứ \(j\) được gọi là ô (\(i\),\(j\)) và được điền giá trị là \(i\) × \(j\). Có \(K\) bạn tham gia chơi trò chơi, mỗi bạn chọn một hình chữ nhật trên bảng số và tô bằng một màu mà mình thích (các hình chữ nhật của các bạn có thể đè lên nhau – tô đè lên).

Yêu cầu: Cho \(N, M\) là kích thước bảng số và \(K\) hình chữ nhật được mô tả bằng ô trái trên và ô phải dưới. Hãy tỉnh tổng những ô chưa được tô màu trên bảng số.

Input

Vào từ thiết bị nhập chuẩn theo khuôn dạng:

• Dòng đầu chứa ba số nguyên \(N, M, K\) mô tả kích thước của bảng số và số lượng hình chữ nhật được tô màu;
• \(K\) dòng sau, mỗi dòng chứa bốn số nguyên \(x, y, u, v\) mô tả ô trái trên (\(x, y\)) và ô phải dưới (\(u, v\)) của một hình chữ nhật. Các ô thoả mãn mô tả một hình chữ nhật nằm trong bảng số.

Output

• Ghi ra thiết bị ra chuẩn một số nguyên duy nhất là phần dư của phép chia của tổng các ô chưa được tô màu trên bảng số cho \(10^9 + 7\).

Scoring

• Subtask #1 (\(20\%\) số điểm): \(K = 1; N, M \leq 100\);
• Subtask #2 (\(10\%\) số điểm): \(K = 1; N, M \leq 10^6\);
• Subtask #3 (\(10\%\) số điểm): \(K = 1; N, M \leq 10^9\);
• Subtask #4 (\(10\%\) số điểm): \(K = 10; N, M \leq 100\);
• Subtask #5 (\(20\%\) số điểm): \(K = 2; N, M \leq 10^6\);
• Subtask #6 (\(10\%\) số điểm): \(K = 2; N, M \leq 10^9\);
• Subtask #7 (\(10\%\) số điểm): \(K = 3; N, M \leq 10^9\);
• Subtask #8 (\(10\%\) số điểm): \(K \leq 10; N, M \leq 10^9\).

Example

3 3 2
1 2 3 3
3 1 3 2

3