Spring Outing Ticket Purchase

Problem Description

The school organizes a spring outing to an amusement park for all students. The tickets are divided into student tickets and adult tickets, with student tickets costing a yuan each and adult tickets costing b yuan each. There are x students participating in the spring outing, and the budget for purchasing tickets is y yuan. Please calculate how many teachers can be bought tickets for with the remaining money after purchasing tickets for x students.

Input

Four integers a, b, x, y, representing the price of student tickets, the price of adult tickets, the number of students, and the budget. It is guaranteed that the budget is sufficient to purchase x student tickets.

Output

An integer representing the maximum number of teachers that can be bought tickets with the remaining money.

Sample InputCopy

20 40 100 2201

Sample OutputCopy

5

Hint

1<=a,b,x<=100, a*x<=y<=100000

Peaks of the Roller Coaster

Problem Description

The roller coaster is very thrilling, but Lele cannot ride it due to motion sickness. To pass the time while waiting, he roughly sketches the shape of the roller coaster track and estimates the heights of n key points. A point is called a “peak” if it is higher than all its adjacent points. Lele thinks that the most exciting moment on the roller coaster is when it passes through a “peak”. Please write a program to calculate the number of “peaks” on the roller coaster.

Input

The first line: a positive integer n; the second line: n positive integers a1, a2, …, ai representing the height of each point.

Output

An integer representing the number of “peaks”.

Sample InputCopy

6
7 6 6 3 9 1

Sample OutputCopy

2

Hint

1<=n<=10^5, 1<=ai<=10^6

Amusement Park Grouping

Problem Description

The students want to watch the water performance at the amusement park. The audience seats are divided into k rows, with m seats in each row. The number of students is n. To arrange the seats properly, the teacher hopes to divide the n students into no more than k groups, with each group having the same number of students and not exceeding m students.

Please write a program to help the teacher determine whether it is possible to achieve the required grouping. If possible, output "yes", otherwise output "no". This problem has multiple sets of data.

Input

The first line: a positive integer T, representing T sets of data. The 2nd to T+1 lines: each line contains three positive integers n, k, m, representing the number of students, the number of rows, and the number of seats per row.

Output

T lines, each line contains a string “yes” or “no”.

Sample InputCopy

2
20 5 10
37 4 20

Sample OutputCopy

yes
no

Hint

1<=T<=1000, 1<=n,m<=10000, 1<=k<=100

Souvenir Shop Lottery

Problem Description

In the amusement park souvenir shop, spending a certain amount allows you to enter a lottery. The staff randomly selects two numbers a and b (where a <= b) from the range 0-9, and all numbers between a and b (inclusive) are considered “egg numbers”. The lottery participant writes a 10-digit positive integer on the ticket, and if at least 6 of the digits are “egg numbers”, they win. The staff collects n tickets, numbered from 1 to n. Please write a program to output the numbers of all winning tickets in order, and finally output the total number of winning tickets.

Input

The first line: three positive integers n, a, b, representing the number of tickets and the two numbers selected by the staff.

The 2nd to n+1 lines: each line contains a number on the ticket, guaranteed to be a 10-digit positive integer without leading zeros.

Output

Several lines, output the winning ticket numbers in ascending order, one number per line. The last line outputs the total number of winning tickets.

Sample InputCopy

4 0 2
1234567890
9876543210
2222222222
1010109823

Sample OutputCopy

3
4
2

Hint

1<=n<=10^5, 1<=a<=b<=9

Condition Satisfied G(a,b)

Problem Description

Define G(a,b) as the new positive integer formed by concatenating two positive integers a and b.

For example: when a is 202 and b is 4, G(a,b)=G(202,4)=2024. Now given two integers n and m, please determine how many pairs (a,b) satisfy G(a,b)=(a+1)*(b+1)-1, where 1<=a<=n, 1<=b<=m, and both a and b are positive integers.

Input

A line containing two positive integers n and m.

Output

A line containing an integer representing the result that meets the requirements of the problem.

Sample InputCopy

1 12

Sample OutputCopy

1

Hint

1<=n,m<=2*10^9