Baby Hop, Giant Hop

Η Samantha, ο βάτραχος, πηδάει ανάμεσα σε νούφαρα που είναι τοποθετημένα σε μια ευθεία γραμμή και απέχουν μεταξύ τους ίσες αποστάσεις. Υπάρχει άπειρος αριθμός από νούφαρα. Τα νούφαρα είναι αριθμημένα διαδοχικά με ακέραιους αριθμούς. Για κάθε ακέραιο αριθμό υπάρχει και ένα αντίστοιχο νούφαρο.

Η Samantha ξεκινά από το νούφαρο με αριθμό ~A~ και θέλει να φτάσει στο νούφαρο με αριθμό ~B~. Μπορεί να κάνει ένα μεγάλο άλμα μήκους ~K~ ή ένα μικρό άλμα μήκους ~1~. Κάθε άλμα μπορεί να γίνει είτε προς τα εμπρός είτε προς τα πίσω.

Η Samantha θέλει να βρει τον ελάχιστο αριθμό από άλματα που χρειάζονται για να μετακινηθεί από το ~A~ στο ~B~. Μερικές φορές, όμως, θέλει να βρει τον δεύτερο μικρότερο αριθμό αλμάτων που χρειάζονται.

Είσοδος

Η πρώτη γραμμή της εισόδου θα περιέχει έναν ακέραιο αριθμό ~A~, που αντιστοιχεί στο αρχικό νούφαρο ~(-10^{18} \le A \le 10^{18})~.

Η δεύτερη γραμμή της εισόδου θα περιέχει έναν ακέραιο αριθμό ~B~, που αντιστοιχεί στο τελικό νούφαρο ~(-10^{18} \le B \le 10^{18})~.

Η τρίτη γραμμή της εισόδου θα περιέχει έναν ακέραιο αριθμό ~K~, που αντιστοιχεί στην απόσταση ενός μεγάλου άλματος ~(2 \le K \le 10^{18})~.

Η τέταρτη γραμμή της εισόδου θα περιέχει έναν ακέραιο αριθμό ~T~, ο οποίος είναι είτε ~1~ είτε ~2~, και υποδεικνύει αν πρέπει να βρεθεί ο ελάχιστος αριθμός από άλματα (όταν ~T=1~) ή ο δεύτερος μικρότερος αριθμός από άλματα (όταν ~T=2~).

Ο ακόλουθος πίνακας δείχνει πώς κατανέμονται οι ~15~ διαθέσιμοι βαθμοί:

Βαθμοί	Όρια	Επιπλέον Περιορισμοί
~5~	~0 \le A,B \le 10,\; K = 2,\; T=1~	Απαιτούνται μόνο άλματα προς τη θετική κατεύθυνση.
~6~	~-10^{18} \le A,B \le 10^{18},\; 2 \le K \le 10^{18},\; T=1~	Κανένας επιπλέον περιορισμός.
~2~	~0 \le A,B \le 100,\; 2 \le K \le 4,\; T = 1~ ή ~T = 2~	Κανένας επιπλέον περιορισμός.
~2~	~-10^{18} \le A,B \le 10^{18},\; 2 \le K \le 10^{18},\; T=1~ ή ~T = 2~	Κανένας επιπλέον περιορισμός.

Σημείωση: Για την επίτευξη της πλήρους βαθμολογίας, οι λύσεις θα πρέπει να μπορούν να διαχειριστούν ακέραιους αριθμούς ~64~-bit. Για παράδειγμα:

• στη C/C++, θα πρέπει να χρησιμοποιείται ο τύπος long long,
• στη Java, θα πρέπει να χρησιμοποιείται ο τύπος long.

Έξοδος

Σε μία μόνο γραμμή, να εκτυπώσετε:

• τον ελάχιστο αριθμό αλμάτων, αν ~T = 1~,
• τον δεύτερο μικρότερο αριθμό αλμάτων, αν ~T = 2~,

που απαιτούνται για τη μετακίνηση από το ~A~ στο ~B~.

Παραδείγματα

input

0
10
3
1

output

4

Επεξήγηση του πρώτου παραδείγματος:

Η Samantha πηδάει στα νούφαρα με αριθμούς ~3~, ~6~ και ~9~, κάνοντας τρία μεγάλα άλματα και στη συνέχεια πηδάει στο νούφαρο με αριθμό ~10~ με ένα μικρό άλμα.

input

0
11
4
1

output

4

Επεξήγηση του δεύτερου παραδείγματος:

Η Samantha πηδάει στα νούφαρα με αριθμούς ~4~, ~8~ και ~12~, κάνοντας τρία μεγάλα άλματα και στη συνέχεια πηδάει στο νούφαρο με αριθμό ~11~ με ένα μικρό άλμα (προς τα πίσω).

input

0
11
4
2

output

5

Επεξήγηση του τρίτου παραδείγματος:

Ο ελάχιστος αριθμός αλμάτων που απαιτούνται ~(4)~ βρέθηκε στο παράδειγμα ~2~. Σε αυτή την είσοδο, ζητείται ο δεύτερος μικρότερος αριθμός αλμάτων, αφού ~T = 2~. Η Samantha πηδάει στα νούφαρα με αριθμούς ~4~ και ~8~ κάνοντας δύο μεγάλα άλματα και στη συνέχεια πηδάει στο νούφαρο με αριθμό ~11~ κάνοντας τρία μικρά άλματα.

input

0
0
3
1

output

0