Problem: A substring of a string is a contiguous subsequence of that string. So, string bca is substring of string abcabc, but string cc is not.

A repeating block is a string formed by concatenating some string with itself. So, string abcabc is a repeating block, but strings abcabd, ababab are not.

You've got a sequence of Latin characters (string). At each step you find the shortest substring that is a repeating block, if there exists more than one you must choose the leftmost. As the substring is of form XX (X — some string) you replace this substring with X, in other words you delete one of the X substrings in the substring. You repeat this process until there remains no repeating block in the string. 

How would the final string looks like? Look at the sample explanation to understand the statement more precise.

Input

In the first line of input you're given a string of small Latin characters with length between 1 to 50000, inclusive.

Output

Print the final string after applying changes.

Examples

Input

abccabc


Output

abc


Input

aaaabaaab


Output

ab


Input

birdbirdbirdistheword


Output

birdistheword

Note

At the first sample the string transforms as follows: abccabc →  abcabc →  abc.

At the second sample the string transforms as follows: aaaabaaab →  aaabaaab →  aabaaab →  abaaab →  abaab →  abab →  ab.

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.Random;
import java.io.OutputStreamWriter;
import java.io.OutputStream;
import java.io.IOException;
import java.io.UncheckedIOException;
import java.util.Objects;
import java.io.Closeable;
import java.io.Writer;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 29);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            FastOutput out = new FastOutput(outputStream);
            DHaveYouEverHeardAboutTheWord solver = new DHaveYouEverHeardAboutTheWord();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class DHaveYouEverHeardAboutTheWord {
        HashData[] hds = HashData.doubleHashData((int) 1e5);
        IntRangeHash rh = new IntRangeHash(hds[0], hds[1], (int) 1e5);
        RollingHash dqL = new RollingHash(hds[0], hds[1], (int) 1e5);
        RollingHash dqR = new RollingHash(hds[0], hds[1], (int) 1e5);

        public void solve(int testNumber, FastInput in, FastOutput out) {
            char[] s = in.rs().toCharArray();
            int n = s.length;
            rh.populate(i -> s[i], n);
            for (int i = 1; i <= n; i++) {
                if (!exist(s, n, i)) {
                    continue;
                }
                //cut
                dqL.clear();
                dqR.clear();
                int wpos = 0;
                for (int j = 0; j < i; j++) {
                    dqL.addLast(s[j]);
                    dqR.addLast(s[i + j]);
                }
                int rpos = 2 * i;
                while (true) {
                    if (dqR.size() < i) {
                        if (rpos >= n) {
                            break;
                        }
                        dqR.addLast(s[rpos++]);
                        continue;
                    }
                    if (dqR.hash() == dqL.hash()) {
                        dqR.clear();
                        continue;
                    }
                    s[wpos++] = (char) dqL.removeFirst();
                    dqL.addLast(dqR.removeFirst());
                }
                while (dqL.size() > 0) {
                    s[wpos++] = (char) dqL.removeFirst();
                }
                while (dqR.size() > 0) {
                    s[wpos++] = (char) dqR.removeFirst();
                }
                if (n == wpos) {
                    throw new IllegalStateException();
                }
                n = wpos;
                rh.populate(j -> s[j], n);
            }

            for (int i = 0; i < n; i++) {
                out.append(s[i]);
            }
        }

        private boolean exist(char[] s, int n, int d) {
            for (int i = d - 1; i + d < n; i += d) {
                if (s[i] != s[i + d]) {
                    continue;
                }
                int l, r;
                l = 1;
                r = d;
                while (l < r) {
                    int m = (l + r + 1) / 2;
                    if (rh.hash(i - m + 1, i) == rh.hash(i + d - m + 1, i + d)) {
                        l = m;
                    } else {
                        r = m - 1;
                    }
                }
                int L = l;
                l = 1;
                r = Math.min(d, n - (i + d));
                while (l < r) {
                    int m = (l + r + 1) / 2;
                    if (rh.hash(i, i + m - 1) == rh.hash(i + d, i + d + m - 1)) {
                        l = m;
                    } else {
                        r = m - 1;
                    }
                }
                int R = l;
                if (L + R > d) {
                    return true;
                }
            }
            return false;
        }

    }

    static class RollingHash {
        HashData hd1;
        HashData hd2;
        IntegerDequeImpl dq;
        long h1;
        long h2;

        public RollingHash(HashData hd1, HashData hd2, int n) {
            this.hd1 = hd1;
            this.hd2 = hd2;
            dq = new IntegerDequeImpl(n + 10);
        }

        public void clear() {
            h1 = h2 = 0;
            dq.clear();
        }

        public int size() {
            return dq.size();
        }

        public void addLast(int x) {
            h1 = (h1 + (long) hd1.pow[dq.size()] * x) % hd1.mod;
            h2 = (h2 + (long) hd2.pow[dq.size()] * x) % hd2.mod;
            dq.addLast(x);
        }

        public int removeFirst() {
            int x = dq.removeFirst();
            h1 = (h1 - x + hd1.mod) * hd1.inv[1] % hd1.mod;
            h2 = (h2 - x + hd2.mod) * hd2.inv[1] % hd2.mod;
            return x;
        }

        public long hash() {
            return DigitUtils.asLong(h1, h2);
        }

    }

    static interface IntegerStack {
    }

    static class Power implements InverseNumber {
        static IntExtGCDObject extGCD = new IntExtGCDObject();
        int mod;

        public Power(int mod) {
            this.mod = mod;
        }

        public int inverse(int x) {
            int ans = inverseExtGCD(x);
//        if(modular.mul(ans, x) != 1){
//            throw new IllegalStateException();
//        }
            return ans;
        }

        public int inverseExtGCD(int x) {
            if (extGCD.extgcd(x, mod) != 1) {
                throw new IllegalArgumentException();
            }
            return DigitUtils.mod(extGCD.getX(), mod);
        }

    }

    static class IntExtGCDObject {
        private int[] xy = new int[2];

        public int extgcd(int a, int b) {
            return ExtGCD.extGCD(a, b, xy);
        }

        public int getX() {
            return xy[0];
        }

    }

    static interface RangeHash {
    }

    static class HashSeed {
        private static int[] seeds = new int[]{11, 13, 17, 29, 31, 41, 43, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103};

        public static Pair<Integer, Integer> getSeed2() {
            int a = seeds[RandomWrapper.INSTANCE.nextInt(seeds.length)];
            int b = a;
            while (b == a) {
                b = seeds[RandomWrapper.INSTANCE.nextInt(seeds.length)];
            }
            return new Pair<>(a, b);
        }

    }

    static interface InverseNumber {
    }

    static class SequenceUtils {
        public static void swap(int[] data, int i, int j) {
            int tmp = data[i];
            data[i] = data[j];
            data[j] = tmp;
        }

    }

    static class FastOutput implements AutoCloseable, Closeable, Appendable {
        private static final int THRESHOLD = 32 << 10;
        private final Writer os;
        private StringBuilder cache = new StringBuilder(THRESHOLD * 2);

        public FastOutput append(CharSequence csq) {
            cache.append(csq);
            return this;
        }

        public FastOutput append(CharSequence csq, int start, int end) {
            cache.append(csq, start, end);
            return this;
        }

        private void afterWrite() {
            if (cache.length() < THRESHOLD) {
                return;
            }
            flush();
        }

        public FastOutput(Writer os) {
            this.os = os;
        }

        public FastOutput(OutputStream os) {
            this(new OutputStreamWriter(os));
        }

        public FastOutput append(char c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput flush() {
            try {
//            boolean success = false;
//            if (stringBuilderValueField != null) {
//                try {
//                    char[] value = (char[]) stringBuilderValueField.get(cache);
//                    os.write(value, 0, cache.length());
//                    success = true;
//                } catch (Exception e) {
//                }
//            }
//            if (!success) {
                os.append(cache);
//            }
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
            return this;
        }

        public void close() {
            flush();
            try {
                os.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        public String toString() {
            return cache.toString();
        }

    }

    static class RandomWrapper {
        private Random random;
        public static final RandomWrapper INSTANCE = new RandomWrapper();

        public RandomWrapper() {
            this(new Random());
        }

        public RandomWrapper(Random random) {
            this.random = random;
        }

        public RandomWrapper(long seed) {
            this(new Random(seed));
        }

        public int nextInt(int l, int r) {
            return random.nextInt(r - l + 1) + l;
        }

        public int nextInt(int n) {
            return random.nextInt(n);
        }

    }

    static class IntRangeHash implements RangeHash {
        HashData hd1;
        HashData hd2;
        int[] h1;
        int[] h2;

        public IntRangeHash(HashData hd1, HashData hd2, int n) {
            this.hd1 = hd1;
            this.hd2 = hd2;
            h1 = new int[n + 10];
            h2 = new int[n + 10];
        }

        private void normalize(int i) {
            h1[i] = DigitUtils.mod(h1[i], hd1.mod);
            h2[i] = DigitUtils.mod(h2[i], hd1.mod);
        }

        public void populate(IntToIntegerFunction function, int n) {
            if (n == 0) {
                return;
            }
            h1[0] = h2[0] = function.apply(0);
            normalize(0);
            for (int i = 1; i < n; i++) {
                h1[i] = h2[i] = function.apply(i);
                normalize(i);
                h1[i] = (int) (((long) h1[i] * hd1.pow[i] + h1[i - 1]) % hd1.mod);
                h2[i] = (int) (((long) h2[i] * hd2.pow[i] + h2[i - 1]) % hd2.mod);
            }
        }

        private int hash1(int l, int r) {
            if (l > r) {
                return 0;
            }
            int ans1 = h1[r];
            if (l > 0) {
                ans1 = (int) (((long) ans1 - h1[l - 1] + hd1.mod) * hd1.inv[l] % hd1.mod);
            }
            return ans1;
        }

        private int hash2(int l, int r) {
            if (l > r) {
                return 0;
            }
            int ans2 = h2[r];
            if (l > 0) {
                ans2 = (int) (((long) ans2 - h2[l - 1] + hd2.mod) * hd2.inv[l] % hd2.mod);
            }
            return ans2;
        }

        public long hash(int l, int r) {
            return DigitUtils.asLong(hash1(l, r), hash2(l, r));
        }

    }

    static interface IntegerIterator {
        boolean hasNext();

        int next();

    }

    static interface IntToIntegerFunction {
        int apply(int x);

    }

    static class DigitUtils {
        public static long INT_TO_LONG_MASK = (1L << 32) - 1;

        private DigitUtils() {
        }

        public static long asLong(int high, int low) {
            return (((long) high) << 32) | (((long) low) & INT_TO_LONG_MASK);
        }

        public static long asLong(long high, long low) {
            return ((high) << 32) | ((low) & INT_TO_LONG_MASK);
        }

        public static int mod(int x, int mod) {
            if (x < -mod || x >= mod) {
                x %= mod;
            }
            if (x < 0) {
                x += mod;
            }
            return x;
        }

    }

    static interface IntegerDeque extends IntegerStack {
    }

    static class Pair<A, B> implements Cloneable {
        public A a;
        public B b;

        public Pair(A a, B b) {
            this.a = a;
            this.b = b;
        }

        public String toString() {
            return "a=" + a + ",b=" + b;
        }

        public int hashCode() {
            return a.hashCode() * 31 + b.hashCode();
        }

        public boolean equals(Object obj) {
            Pair<A, B> casted = (Pair<A, B>) obj;
            return Objects.equals(casted.a, a) && Objects.equals(casted.b, b);
        }

        public Pair<A, B> clone() {
            try {
                return (Pair<A, B>) super.clone();
            } catch (CloneNotSupportedException e) {
                throw new RuntimeException(e);
            }
        }

    }

    static class FastInput {
        private final InputStream is;
        private StringBuilder defaultStringBuf = new StringBuilder(1 << 13);
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    bufLen = -1;
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public String rs() {
            return readString();
        }

        public String readString(StringBuilder builder) {
            skipBlank();

            while (next > 32) {
                builder.append((char) next);
                next = read();
            }

            return builder.toString();
        }

        public String readString() {
            defaultStringBuf.setLength(0);
            return readString(defaultStringBuf);
        }

    }

    static class IntegerDequeImpl implements IntegerDeque {
        private int[] data;
        private int bpos;
        private int epos;
        private static final int[] EMPTY = new int[0];
        private int n;

        public IntegerDequeImpl(int cap) {
            if (cap == 0) {
                data = EMPTY;
            } else {
                data = new int[cap];
            }
            bpos = 0;
            epos = 0;
            n = cap;
        }

        private void expandSpace(int len) {
            while (n < len) {
                n = Math.max(n + 10, n * 2);
            }
            int[] newData = new int[n];
            if (bpos <= epos) {
                if (bpos < epos) {
                    System.arraycopy(data, bpos, newData, 0, epos - bpos);
                }
            } else {
                System.arraycopy(data, bpos, newData, 0, data.length - bpos);
                System.arraycopy(data, 0, newData, data.length - bpos, epos);
            }
            epos = size();
            bpos = 0;
            data = newData;
        }

        public IntegerIterator iterator() {
            return new IntegerIterator() {
                int index = bpos;


                public boolean hasNext() {
                    return index != epos;
                }


                public int next() {
                    int ans = data[index];
                    index = IntegerDequeImpl.this.next(index);
                    return ans;
                }
            };
        }

        public int removeFirst() {
            int ans = data[bpos];
            bpos = next(bpos);
            return ans;
        }

        public void addLast(int x) {
            ensureMore();
            data[epos] = x;
            epos = next(epos);
        }

        public void clear() {
            bpos = epos = 0;
        }

        private int next(int x) {
            return x + 1 >= n ? 0 : x + 1;
        }

        private void ensureMore() {
            if (next(epos) == bpos) {
                expandSpace(n + 1);
            }
        }

        public int size() {
            int ans = epos - bpos;
            if (ans < 0) {
                ans += data.length;
            }
            return ans;
        }

        public String toString() {
            StringBuilder builder = new StringBuilder();
            for (IntegerIterator iterator = iterator(); iterator.hasNext(); ) {
                builder.append(iterator.next()).append(' ');
            }
            return builder.toString();
        }

    }

    static class ExtGCD {
        public static int extGCD(int a, int b, int[] xy) {
            if (a >= b) {
                return extGCD0(a, b, xy);
            }
            int ans = extGCD0(b, a, xy);
            SequenceUtils.swap(xy, 0, 1);
            return ans;
        }

        private static int extGCD0(int a, int b, int[] xy) {
            if (b == 0) {
                xy[0] = 1;
                xy[1] = 0;
                return a;
            }
            int ans = extGCD0(b, a % b, xy);
            int x = xy[0];
            int y = xy[1];
            xy[0] = y;
            xy[1] = x - a / b * y;
            return ans;
        }

    }

    static class HashData {
        public int mod;
        public int[] inv;
        public int[] pow;
        public int x;

        public HashData(int n, int x, int p) {
            this.mod = p;
            this.x = x;
            inv = new int[n + 10];
            pow = new int[n + 10];
            inv[0] = 1;
            pow[0] = 1;
            int invX = new Power(p).inverse(x);
            for (int i = 1; i < n + 10; i++) {
                inv[i] = (int) ((long) inv[i - 1] * invX % mod);
                pow[i] = (int) ((long) pow[i - 1] * x % mod);
            }
        }

        public HashData(int n, int x) {
            this(n, x, (int) 1e9 + 7);
        }

        public HashData(int n) {
            this(n, RandomWrapper.INSTANCE.nextInt(3, (int) 1e9 + 6), (int) 1e9 + 7);
        }

        public static HashData[] doubleHashData(int n) {
            Pair<Integer, Integer> pairs = HashSeed.getSeed2();
            return new HashData[]{new HashData(n, pairs.a), new HashData(n, pairs.b)};
        }

    }
}