A - Beru-taxi(706A - Beru-taxi)

                                 706A - Beru-taxi

Vasiliy lives at point (a, b) of the coordinate plane. He is hurrying up to work so he wants to get out of his house as soon as possible. New app suggested n available Beru-taxi nearby. The i-th taxi is located at point (x i, y i) and moves with a speed v i.

Consider that each of n drivers will move directly to Vasiliy and with a maximum possible speed. Compute the minimum time when Vasiliy will get in any of Beru-taxi cars.

Input

The first line of the input contains two integers a and b ( - 100 ≤ a, b ≤ 100) — coordinates of Vasiliy's home.

The second line contains a single integer n (1 ≤ n ≤ 1000) — the number of available Beru-taxi cars nearby.

The i-th of the following n lines contains three integers x i, y i and v i ( - 100 ≤ x i, y i ≤ 100, 1 ≤ v i ≤ 100) — the coordinates of the i-th car and its speed.

It's allowed that several cars are located at the same point. Also, cars may be located at exactly the same point where Vasiliy lives.

Output

Print a single real value — the minimum time Vasiliy needs to get in any of the Beru-taxi cars. You answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if .

Examples

input

Copy

0 0
2
2 0 1
0 2 2

output

Copy

1.00000000000000000000

input

Copy

1 3
3
3 3 2
-2 3 6
-2 7 10

output

Copy

0.50000000000000000000

Note

In the first sample, first taxi will get to Vasiliy in time 2, and second will do this in time 1, therefore 1 is the answer.

In the second sample, cars 2 and 3 will arrive simultaneously.

---

#include<bits/stdc++.h>
using namespace std;
int main()
      {
      int t;
       float a,b,v;
      float x,y;
      float dis,mn=1000,ans=0;
      cin>>x>>y;
      cin>>t;
 
      while(t--)
      {
      cin>>a>>b>>v;
      if(a==x and b==y) {ans=1;}
      dis=sqrt( (x-a)*(x-a) +(y-b)*(y-b)    );
      mn = min(mn, dis/v);
 
      }
      if(ans) cout<<"0.00000000000000000000"<<endl;
     else printf("%.20f\n",mn);
 
      return 0;}

787A - The Monster

787A - The Monster.cpp 

A monster is chasing after Rick and Morty on another planet. They're so frightened that sometimes they scream. More accurately, Rick screams at times b, b + a, b + 2a, b + 3a, ... and Morty screams at times d, d + c, d + 2c, d + 3c, ....

The Monster will catch them if at any point they scream at the same time, so it wants to know when it will catch them (the first time they scream at the same time) or that they will never scream at the same time.

Input

The first line of input contains two integers a and b (1 ≤ a, b ≤ 100).

The second line contains two integers c and d (1 ≤ c, d ≤ 100).

Output

Print the first time Rick and Morty will scream at the same time, or  - 1 if they will never scream at the same time.

Examples

input

Copy

20 2
9 19

output

Copy

82

input

Copy

2 1
16 12

output

Copy

-1

Note

In the first sample testcase, Rick's 5th scream and Morty's 8th time are at time 82.

In the second sample testcase, all Rick's screams will be at odd times and Morty's will be at even times, so they will never scream at the same time.

1. ///bismillah
2. #include<iostream>
3. using namespace std;
4. int main(){
5. long long a,b,c,d,f=0;
6. long int sum1[300],sum2[300];
7. cin>>a>>b;
8. cin>>c>>d;
9. for(int i=0;i<101;i++)
10. { sum1[i]= b+i*a;
11.  
12. }
13. for(int i=0;i<101;i++)
14. { sum2[i]= d+i*c;
15.  
16. }
17. for(int j=0;j<101;j++){
18. for(int i=0;i<101;i++) {
19. if(sum2[j]==sum1[i])
20. { cout<<sum2[j]; f=1; break; }
21.  
22. }
23. if(f==1) break;}
24.  
25.  
26. if(f==0) cout<<-1;
27. return 0;
28.  
29.  
30. }
31.  

680A - Bear and Five Cards

1. 680A - Bear and Five Cards

A. Bear and Five Cards

 

A little bear Limak plays a game. He has five cards. There is one number written on each card. Each number is a positive integer.

Limak can discard (throw out) some cards. His goal is to minimize the sum of numbers written on remaining (not discarded) cards.

He is allowed to at most once discard two or three cards with the same number. Of course, he won't discard cards if it's impossible to choose two or three cards with the same number.

Given five numbers written on cards, cay you find the minimum sum of numbers on remaining cards?

Input

The only line of the input contains five integers t 1, t 2, t 3, t 4 and t 5 (1 ≤ t i ≤ 100) — numbers written on cards.

Output

Print the minimum possible sum of numbers written on remaining cards.

Examples

input

Copy

7 3 7 3 20

output

Copy

26

input

Copy

7 9 3 1 8

output

Copy

28

input

Copy

10 10 10 10 10

output

Copy

20

Note

In the first sample, Limak has cards with numbers 7, 3, 7, 3 and 20. Limak can do one of the following.

• Do nothing and the sum would be 7 + 3 + 7 + 3 + 20 = 40.
• Remove two cards with a number 7. The remaining sum would be 3 + 3 + 20 = 26.
• Remove two cards with a number 3. The remaining sum would be 7 + 7 + 20 = 34.

You are asked to minimize the sum so the answer is 26.

In the second sample, it's impossible to find two or three cards with the same number. Hence, Limak does nothing and the sum is 7 + 9 + 1 + 3 + 8 = 28.

In the third sample, all cards have the same number. It's optimal to discard any three cards. The sum of two remaining numbers is 10 + 10 = 20.

1. 
   
2. #include<bits/stdc++.h>
3. using namespace std;
4. int main(){
5. int a[5],sum=0,x=0,y=0;
6. int b[100000]={0};
7. for(int i=0;i<5;i++)
8. {cin>>a[i];
9. b[a[i]]++;
10. if( b[a[i]]==2) x=max(x,a[i]);
11. else if( b[a[i]]==3) y=a[i];
12.  
13. sum = sum +a[i];}
14.  
15.  
16. cout<<sum-max(2*x,3*y);
17.  
18. return 0; }

676A - Nicholas and Permutation

1. A. Nicholas and Permutation

    

   Nicholas has an array a that contains n distinct integers from 1 to n. In other words, Nicholas has a permutation of size n.

   Nicholas want the minimum element (integer 1) and the maximum element (integer n) to be as far as possible from each other. He wants to perform exactly one swap in order to maximize the distance between the minimum and the maximum elements. The distance between two elements is considered to be equal to the absolute difference between their positions.

   Input

   The first line of the input contains a single integer n (2 ≤ n ≤ 100) — the size of the permutation.

   The second line of the input contains n distinct integers a 1, a 2, ..., a n (1 ≤ a i ≤ n), where a i is equal to the element at the i-th position.

   Output

   Print a single integer — the maximum possible distance between the minimum and the maximum elements Nicholas can achieve by performing exactly one swap.

   Examples

   input

   Copy

   5
   4 5 1 3 2

   output

   Copy

   3

   input

   Copy

   7
   1 6 5 3 4 7 2

   output

   Copy

   6

   input

   Copy

   6
   6 5 4 3 2 1

   output

   Copy

   5

   Note

   In the first sample, one may obtain the optimal answer by swapping elements 1 and 2.

   In the second sample, the minimum and the maximum elements will be located in the opposite ends of the array if we swap 7 and 2.

   In the third sample, the distance between the minimum and the maximum elements is already maximum possible, so we just perform some unnecessary swap, for example, one can swap 5 and 2.
2. 
   
3. 
   
4. 
   
5. 
   
6. 
   
7. 
   
8. #include<bits/stdc++.h>
9. using namespace std;
10. int main()
11. {
12. int n; cin>>n;
13. int a[n];int x;
14. vector<pair<int,int>>v;
15. for(int i=1;i<=n;i++)
16. { cin>>x;
17. v.push_back(make_pair(x,i));
18.  
19. }
20. sort(v.begin(),v.end());
21.  
22. {
23. int a=v[0].second;///5
24. int b=v[n-1].second;///3
25.  
26. cout << max(max(n - b, b - 1), max(n - a, a - 1));
27.  
28.  
29.  
30. }
31.  
32.  
33.  

670A - Holidays

670A - Holidays

1. 
   A. Holidays

    

   On the planet Mars a year lasts exactly n days (there are no leap years on Mars). But Martians have the same weeks as earthlings — 5 work days and then 2 days off. Your task is to determine the minimum possible and the maximum possible number of days off per year on Mars.

   Input

   The first line of the input contains a positive integer n (1 ≤ n ≤ 1 000 000) — the number of days in a year on Mars.

   Output

   Print two integers — the minimum possible and the maximum possible number of days off per year on Mars.

   Examples

   input

   Copy

   14
   

   output

   Copy

   4 4
   

   input

   Copy

   2
   

   output

   Copy

   0 2
   

   Note

   In the first sample there are 14 days in a year on Mars, and therefore independently of the day a year starts with there will be exactly 4 days off .

   In the second sample there are only 2 days in a year on Mars, and they can both be either work days or days off.

2. 
   
3. 
   
4. 
   
5. #include<iostream>
6. using namespace std;
7. int main()
8. {
9. long n;
10. cin>>n;
11. long d=0,x=0;int i=1;
12. long m=n;
13. ///max
14. d=n/7;
15. x= n- 7*d;
16. if(x>=2 and x!=0) x=2;
17. else if(x<2 and x!=0) x=1;
18.  
19. ///min
20. int mn=0;
21.  
22. while(m--){
23. n=n-5;
24. if(n>=2 and n!=0){ mn+=2; n=n-2;}
25. else if(n>=1 and n!=0 ){ mn+=1; n=n-1;}
26. //cout<<n<<" ";
27. }
28. cout<<mn<<" ";
29. cout<<2*d+x;
30.  
31. return 0;
32. }