d

// Define the StringList interface
public interface StringList {
    boolean add(int index, String item) throws StringListException;
    String get(int index) throws StringListException;
    int size();
    boolean isEmpty();
    String makeString(String start, String sep, String end);
    String toString();
    void clear();
    String remove(int index) throws StringListException;
    boolean contains(int start, String target) throws StringListException;
    boolean add(int index, StringList itemList) throws StringListException;
    StringList reverse();
    StringList slice(int start, int stop) throws StringListException;
}

// Define custom exceptions for index out of bounds and illegal arguments
class StringListException extends Exception {
    public StringListException(String message) {
        super(message);
    }
}

class IndexOutOfBoundsError extends StringListException {
    public IndexOutOfBoundsError() {
        super("Index out of bounds");
    }
}

class IllegalArgumentError extends StringListException {
    public IllegalArgumentError() {
        super("Illegal argument error");
    }
}

// Abstract class for shared logic
abstract class BaseStringList implements StringList {
    protected int size;

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public String makeString(String start, String sep, String end) {
        if (size == 0) return start + end;
        StringBuilder result = new StringBuilder(start);
        try {
            result.append(get(0));
            for (int i = 1; i < size; i++) {
                result.append(sep).append(get(i));
            }
        } catch (StringListException e) {
            return start + end;
        }
        result.append(end);
        return result.toString();
    }

    public String toString() {
        return makeString("[", ", ", "]");
    }

    public boolean contains(int start, String target) throws StringListException {
        if (start < 0) return false;
        for (int i = start; i < size; i++) {
            if (get(i).equals(target)) return true;
        }
        return false;
    }

    public boolean add(int index, StringList itemList) throws StringListException {
        if (index < 0 || index > size) throw new IndexOutOfBoundsError();
        for (int i = 0; i < itemList.size(); i++) {
            add(index++, itemList.get(i));
        }
        return !itemList.isEmpty();
    }

    public StringList reverse() {
        StringList result = createInstance();
        try {
            for (int i = 0; i < size; i++) {
                result.add(i, get(size - i - 1));
            }
        } catch (StringListException e) {
            e.printStackTrace();
        }
        return result;
    }

    public StringList slice(int start, int stop) throws StringListException {
        if (start < 0 || stop > size || start > stop) throw new IndexOutOfBoundsError();
        StringList result = createInstance();
        for (int i = start; i < stop; i++) {
            result.add(result.size(), get(i));
        }
        return result;
    }

    // Abstract method to create an instance of the concrete class
    protected abstract StringList createInstance();
}

// ArrayStringList implementation backed by a basic Java array
class ArrayStringList extends BaseStringList {
    private String[] items;

    public ArrayStringList() {
        size = 0;
        items = new String[2];  // Initially small array
    }

    // Method to resize the array when it reaches capacity
    private void reallocateIfNeeded() {
        if (size == items.length) {
            // Resize array to 1.5x its current length
            String[] newItems = new String[(int) (items.length * 1.5)];
            System.arraycopy(items, 0, newItems, 0, size);  // Copy items to new array
            items = newItems;
        }
    }

    public boolean add(int index, String item) throws StringListException {
        if (item == null || item.isEmpty()) throw new IllegalArgumentError();
        if (index < 0 || index > size) throw new IndexOutOfBoundsError();

        reallocateIfNeeded();  // Resize if necessary

        // Shift elements to the right to make space for the new item
        for (int i = size; i > index; i--) {
            items[i] = items[i - 1];
        }

        items[index] = item;
        size++;
        return true;
    }

    public String get(int index) throws StringListException {
        if (index < 0 || index >= size) throw new IndexOutOfBoundsError();
        return items[index];
    }

    public void clear() {
        size = 0;  // Simply reset the size to 0
    }

    public String remove(int index) throws StringListException {
        if (index < 0 || index >= size) throw new IndexOutOfBoundsError();

        String removedItem = items[index];

        // Shift elements to the left to fill the gap
        for (int i = index; i < size - 1; i++) {
            items[i] = items[i + 1];
        }

        size--;
        return removedItem;
    }

    @Override
    protected StringList createInstance() {
        return new ArrayStringList();
    }
}

// Node class for linked list
class Node {
    private String item;
    private Node next;

    public Node(String item, Node next) {
        this.item = item;
        this.next = next;
    }

    public String getItem() {
        return item;
    }

    public void setItem(String item) {
        this.item = item;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}

// LinkedStringList implementation
class LinkedStringList extends BaseStringList {
    private Node head;

    public LinkedStringList() {
        size = 0;
        head = null;
    }

    public boolean add(int index, String item) throws StringListException {
        if (item == null || item.isEmpty()) throw new IllegalArgumentError();
        if (index < 0 || index > size) throw new IndexOutOfBoundsError();

        if (index == 0) {
            head = new Node(item, head);
        } else {
            Node current = head;
            for (int i = 0; i < index - 1; i++) {
                current = current.getNext();
            }
            Node newNode = new Node(item, current.getNext());
            current.setNext(newNode);
        }
        size++;
        return true;
    }

    public String get(int index) throws StringListException {
        if (index < 0 || index >= size || head == null) throw new IndexOutOfBoundsError();
        Node current = head;
        for (int i = 0; i < index; i++) {
            current = current.getNext();
        }
        return current.getItem();
    }

    public void clear() {
        head = null;
        size = 0;
    }

    public String remove(int index) throws StringListException {
        if (index < 0 || index >= size) throw new IndexOutOfBoundsError();
        String item;

        if (index == 0) {
            item = head.getItem();
            head = head.getNext();
        } else {
            Node current = head;
            for (int i = 0; i < index - 1; i++) {
                current = current.getNext();
            }
            item = current.getNext().getItem();
            current.setNext(current.getNext().getNext());
        }

        size--;
        return item;
    }

    @Override
    protected StringList createInstance() {
        return new LinkedStringList();
    }
}